Hogyan lehet a lehető legkisebb számot kialakítani egy adott számból a JavaScript-ben

Ebben az oktatóanyagban egy algoritmust valósítunk meg a lehető legkisebb szám kialakításához az ES6 segítségével.

Input: 55010 7652634
Output: 10055 2345667

Megjegyzés : Az átalakított szám nem kezdődhet 0-val, ha legalább egy nem nulla karaktert tartalmaz.

Két különböző megközelítést fogunk használni a probléma megoldására. Mindent ES6-ban írunk.

  • Az első megközelítésben feltételezzük, hogy a megadott szám karakterlánc formátumban van, és megoldjuk azt rendezéssel, amely O (nlogn) értéket vesz fel.
  • A második megközelítésben numerikus értékkel oldjuk meg O (d) idővel, ahol d a számjegyek száma.

O (nlogn) rendezés.

Végrehajtás

  • Átalakítjuk a számot karaktertömbökké, majd rendezzük a tömböt.
  • Rendezés után ellenőrizzük, hogy a tömb első karaktere 0-e.
  • Ha nem 0, akkor csatlakozunk a tömbhöz és visszaadjuk.
  • Ha 0, akkor megtaláljuk az első nem nulla számot, felcseréljük 0-val és visszaadjuk.
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(''); }

A program futtatása

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

Hogyan működik

Először hoztuk létre a like karaktereket ['5', '5', '0', '1', 0]. Ezután ezt rendezzük. ['0', '0', '1', '5', '5']Ezután megtaláljuk az első nem nulla elemet, és felcseréljük az első nulla elemekkel, például ['1', '0', '0', '5', '5']. Most készen áll a legkisebb számunk, csak össze kell összefűznünk és vissza kell adnunk.

További információ a felosztásról (), rendezésről (), csatlakozásról ().

Időkomplexitás: O (nlogn).

Tér komplexitás: O (n).

Az idő és a tér összetettségének magyarázata

Olyan karaktertömböt hozunk létre, amely O (n) időt vesz igénybe. Ezután a tömb rendezése O (nlogn) értéket vesz fel.

Ezután megtaláljuk a legkisebb nem nulla szám indexét, amely legrosszabb esetben O (n) -et vehet fel, és a tömbhöz csatlakozva a húr létrehozásához O (n) lesz. Mivel ezek az összes művelet egymás után futnak. Tehát az idő bonyolultsága O (n + nlogn + n + n) = O (nlogn).

A karakterláncból tömb karaktert hozunk létre, így a tér bonyolultsága O (n).

Az O (logn) numerikus érték felhasználásával.

Ebben a megközelítésben van egy hátrány: ha a szám csak nullákat tartalmaz, akkor egyetlen nullát ad vissza.

Végrehajtás

  • Létrehozunk egy 0 és 9 közötti számtömböt.
  • Ezután nyomon követjük a számban lévő számjegyeket, növelve azok számát a tömbben.
  • Ezt követően megtaláljuk a legkisebb, nem nulla számjegyet, és 1-gyel csökkentjük a számát.
  • Végül a számot úgy állítjuk elő, hogy növekvő sorrendbe rendezzük, és visszaadjuk az eredményt.
  • Ez a megoldás a számlálási sorrenden alapul.
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; }

A program futtatása

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

Időkomplexitás: O (nlogn).

Tér komplexitás: O (1).

Az idő és a tér összetettségének magyarázata

Minden számjegyet eltávolítunk a számból, és növeljük a megfelelő számot egy tömbben, amely O (logn) értéket vesz fel. Ezután megtaláljuk az O (10) tömbjének legkisebb, nem nulla számát.

Ezt követően átrendezzük a számokat, hogy létrehozzuk a legkisebb számot O-ban (10 * logn). Az idő komplexitása O (logn + 10+ 10logn) = O (logn) vagy O (d), ahol d a számjegyek száma

Állandó teret használunk (10 szám tömb), így a tér bonyolultsága O (1).

Ha tetszett ez a cikk, kérjük, adja meg? És ossza meg! Ha bármilyen kérdése van ezzel kapcsolatban, kérdezzen bátran.

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.