So bilden Sie aus einer bestimmten Zahl in JavaScript die kleinstmögliche Zahl

In diesem Tutorial implementieren wir einen Algorithmus, um mit ES6 die kleinstmögliche Zahl zu bilden.

Input: 55010 7652634
Output: 10055 2345667

Hinweis : Die transformierte Zahl sollte nicht mit 0 beginnen, wenn sie mindestens ein Zeichen ungleich Null enthält.

Wir werden zwei verschiedene Ansätze verwenden, um dieses Problem zu lösen. Alles wird in ES6 geschrieben.

  • Im ersten Ansatz nehmen wir an, dass die angegebene Zahl im Zeichenfolgenformat vorliegt, und lösen sie mithilfe einer Sortierung, die O (nlogn) annimmt.
  • Im zweiten Ansatz werden wir mit einem numerischen Wert mit der Zeit O (d) lösen, wobei d die Anzahl der Ziffern ist.

Verwenden der Sortierung O (nlogn).

Implementierung

  • Wir werden die Zahl in das Zeichenarray konvertieren und dieses Array dann sortieren.
  • Nach dem Sortieren prüfen wir, ob das erste Zeichen im Array 0 ist.
  • Wenn es nicht 0 ist, werden wir dem Array beitreten und es zurückgeben.
  • Wenn es 0 ist, finden wir die erste Zahl ungleich Null und tauschen sie mit 0 aus und geben sie zurück.
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(''); }

Ausführen des Programms

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('');*/

Wie es funktioniert

Wir haben zuerst das Array von Zeichen wie erstellt ['5', '5', '0', '1', 0]. Dann sortieren wir dies nach ['0', '0', '1', '5', '5']Danach finden wir das erste Nicht-Null-Element und tauschen es mit den ersten Null-Elementen wie aus ['1', '0', '0', '5', '5']. Jetzt haben wir unsere kleinste Nummer fertig, wir müssen sie nur noch verketten und zurückgeben.

Erfahren Sie mehr über split (), sort (), join ().

Zeitkomplexität: O (nlogn).

Raumkomplexität: O (n).

Erklärung der Komplexität von Zeit und Raum

Wir erstellen ein Zeichenarray, das O (n) Zeit benötigt. Dann nimmt das Sortieren des Arrays O (nlogn).

Danach finden wir den Index der kleinsten Nicht-Null-Zahl, die im schlimmsten Fall O (n) annehmen kann, und das Verbinden des Arrays zum Erstellen der Zeichenfolge nimmt O (n). Da diese alle Operationen nacheinander ausgeführt werden. Die zeitliche Komplexität ist also O (n + nlogn + n + n) = O (nlogn).

Wir erstellen ein Array von Zeichen aus der Zeichenfolge, sodass die Raumkomplexität O (n) ist.

Verwenden des numerischen Werts O (logn).

Dieser Ansatz hat einen Nachteil: Wenn die Zahl nur Nullen enthält, wird eine einzelne Null zurückgegeben.

Implementierung

  • Wir werden ein Array von Zahlen von 0 bis 9 erstellen.
  • Dann werden wir die in der Zahl vorhandenen Ziffern verfolgen, indem wir ihre Anzahl im Array erhöhen.
  • Danach finden wir die kleinste Ziffer ungleich Null und verringern ihre Anzahl um 1.
  • Am Ende erstellen wir die Nummer neu, indem wir sie in aufsteigender Reihenfolge anordnen und das Ergebnis zurückgeben.
  • Diese Lösung basiert auf der Zählsortierung.
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; }

Programm ausführen

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*/

Zeitkomplexität: O (nlogn).

Raumkomplexität: O (1).

Erklärung der Komplexität von Zeit und Raum

Wir entfernen jede Ziffer aus der Zahl und erhöhen ihre jeweilige Anzahl in einem Array, das O (logn) annimmt. Dann finden wir die kleinste Zahl ungleich Null aus dem Array in O (10).

Danach ordnen wir die Ziffern neu an, um die kleinste Zahl in O (10 * logn) zu erstellen. Die zeitliche Komplexität ist O (logn + 10+ 10logn) = O (logn) oder O (d), wobei d die Anzahl der Ziffern ist

Wir verwenden konstanten Raum (ein Array von 10 Zahlen), daher ist die Raumkomplexität O (1).

Wenn Ihnen dieser Artikel gefallen hat, geben Sie ihm bitte etwas und teilen Sie ihn! Wenn Sie Fragen dazu haben, können Sie mich gerne fragen.

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.