Comment former le plus petit nombre possible à partir d'un nombre donné en JavaScript

Dans ce tutoriel, nous allons implémenter un algorithme pour former le plus petit nombre possible avec ES6.

Input: 55010 7652634
Output: 10055 2345667

Remarque : le nombre transformé ne doit pas commencer par 0 s'il comporte au moins un caractère différent de zéro.

Nous allons utiliser deux approches différentes pour résoudre ce problème. Tout sera écrit dans ES6.

  • Dans la première approche, nous supposerons que le nombre fourni est au format chaîne et le résoudrons en utilisant un tri qui prendra O (nlogn).
  • Dans la deuxième approche, nous résoudrons avec une valeur numérique avec un temps O (d), où d est le nombre de chiffres.

Utilisation du tri O (nlogn).

la mise en oeuvre

  • Nous convertirons le nombre en tableau de caractères, puis trierons ce tableau.
  • Après le tri, nous vérifierons si le premier caractère du tableau est 0.
  • Si ce n'est pas 0, nous rejoindrons le tableau et le retournerons.
  • Si c'est 0, nous trouverons le premier nombre différent de zéro et l'échangerons avec 0 et le retournerons.
function smallestPossibleNumber(num){
//Create a character array and sort it in ascending orderlet sorted = num.split('').sort();
//Check if first character is not 0 then join and return it if(sorted[0] != '0'){ return sorted.join('');}
//find the index of the first non - zero character let index = 0; for(let i = 0; i  "0"){ index = i; break; } }
//Swap the indexes let temp = sorted[0]; sorted[0] = sorted[index]; sorted[index] = temp;
//return the string after joining the characters of array return sorted.join(''); }

Exécution du programme

Input:console.log(smallestPossibleNumber('55010'));console.log(smallestPossibleNumber('7652634'));console.log(smallestPossibleNumber('000001'));console.log(smallestPossibleNumber('000000'));
Output:100552345667100000000000
/*How it works let sorted = num.split('').sort(); = ['5','5','0','1','0'].sort() = ['0','0','1','5','5'] if(sorted[0] != '0'){ // '0' != '0' condition fails return sorted.join(''); } //Find the index of the first non - zero character let index = 0; for(let i = 0; i  '0'){ // '1' > '0' index = i; // index = 2; break; // break; } } //swap the index var temp = sorted[0]; sorted[0] = sorted[index]; sorted[index] = temp; //return the string return sorted.join('');*/

Comment ça fonctionne

Nous avons d'abord créé le tableau de caractères comme ['5', '5', '0', '1', 0]. Ensuite, nous trions ceci dans ['0', '0', '1', '5', '5']Après cela, nous trouvons le premier élément non nul et l'échangerons avec les premiers éléments zéro comme ['1', '0', '0', '5', '5']. Maintenant que nous avons notre plus petit nombre prêt, il suffit de les concaténer et de le renvoyer.

En savoir plus sur les fonctions split (), sort (), join ().

Complexité temporelle: O (nlogn).

Complexité spatiale: O (n).

Explication de la complexité du temps et de l'espace

Nous créons un tableau de caractères qui prendra O (n) temps. Ensuite, le tri du tableau prendra O (nlogn).

Après cela, nous trouvons l'indice du plus petit nombre non nul qui peut prendre O (n) dans le pire des cas et joindre le tableau pour créer la chaîne prendra O (n). Comme toutes ces opérations se déroulent les unes après les autres. La complexité en temps est donc O (n + nlogn + n + n) = O (nlogn).

Nous créons un tableau de caractères à partir de la chaîne, donc la complexité de l'espace est O (n).

Utilisation de la valeur numérique O (logn).

Il y a un inconvénient dans cette approche: si le nombre ne contient que des zéros, il renverra un seul zéro.

la mise en oeuvre

  • Nous allons créer un tableau de nombres de 0 à 9.
  • Ensuite, nous garderons une trace des chiffres présents dans le nombre en augmentant leur nombre dans le tableau.
  • Après cela, nous trouverons le plus petit chiffre différent de zéro et diminuerons son nombre de 1.
  • En fin de compte, nous recréerons le nombre en les organisant par ordre croissant et nous retournerons le résultat.
  • Cette solution est basée sur le tri de comptage.
function smallestPossibleNumber(num) { // initialize frequency of each digit to Zero let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // count frequency of each digit in the number while (num > 0){ let d = parseInt(num % 10); // extract last digit freq[d]++; // increment counting num = parseInt(num / 10); //remove last digit }
// Set the LEFTMOST digit to minimum expect 0 let result = 0; for (let i = 1 ; i <= 9 ; i++) { if (freq[i] != 0) { result = i; freq[i]--; break; } } // arrange all remaining digits // in ascending order for (let i = 0 ; i <= 9 ; i++) { while (freq[i]-- != 0){ result = result * 10 + i; } } return result; }

Lancer le programme

Input:console.log(smallestPossibleNumber('55010'));console.log(smallestPossibleNumber('7652634'));console.log(smallestPossibleNumber('000001'));console.log(smallestPossibleNumber('000000'));
Output:10055234566710
/* How it works // initialize frequency of each digit to Zero let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // count frequency of each digit in the number while (num > 0){ let d = parseInt(num % 10); // extract last digit freq[d]++; // increment counting num = parseInt(num / 10); //remove last digit } //After incrementing count //freq = [2, 1, 0, 0, 0, 2, 0, 0, 0, 0] // Set the LEFTMOST digit to minimum expect 0 let result = 0; for (let i = 1 ; i <= 9 ; i++) { if (freq[i] != 0) { result = i; freq[i]--; break; } } // result = 1 // arrange all remaining digits // in ascending order for (let i = 0 ; i <= 9 ; i++) { while (freq[i]-- != 0){ result = result * 10 + i; } }
 //10 //100 //1005 //10055 //10055 return result*/

Complexité temporelle: O (nlogn).

Complexité spatiale: O (1).

Explication de la complexité du temps et de l'espace

Nous supprimons chaque chiffre du nombre et incrémentons son compte respectif dans un tableau qui prendra O (logn). Ensuite, nous trouvons le plus petit nombre non nul du tableau dans O (10).

Après cela, nous réorganisons les chiffres pour créer le plus petit nombre en O (10 * logn). La complexité temporelle est O (logn + 10+ 10logn) = O (logn) ou O (d), où d est le nombre de chiffres

Nous utilisons un espace constant (un tableau de 10 nombres), donc la complexité de l'espace est O (1).

Si vous avez aimé cet article, donnez-en-lui quelques-uns et partagez-le! Si vous avez des questions à ce sujet, n'hésitez pas à me les poser.

For more like this and algorithmic solutions in Javascript, follow me on Twitter. I write about ES6, React, Nodejs, Data structures, and Algorithms on learnersbucket.com.