de Prashant Yadav

Cum se formează cel mai mic număr posibil dintr-un număr dat în JavaScript

În acest tutorial, vom implementa un algoritm pentru a forma cel mai mic număr posibil ES6.

Cum se formeaza cel mai mic numar posibil dintr un numar
Sursa: Pixabay
Input: 55010 7652634
Output: 10055 2345667

Notă: Numărul transformat nu ar trebui să înceapă cu 0 dacă are cel puțin un caracter diferit de zero.

Vom folosi două abordări diferite pentru a rezolva această problemă. Totul va fi scris în ES6.

  • În prima abordare, vom presupune că numărul furnizat este în format șir și îl vom rezolva folosind sortarea care va lua O (nlogn).
  • În cea de-a doua abordare, vom rezolva cu valoare numerică cu O (d) timp, unde d este numărul de cifre.

Folosind sortarea O (nlogn).

Implementare

  • Vom converti numărul în matricea de caractere și apoi vom sorta matricea respectivă.
  • După sortare vom verifica dacă primul caracter din matrice este 0.
  • Dacă nu este 0, atunci ne vom alătura matricei și o vom returna.
  • Dacă este 0 atunci vom găsi primul număr diferit de zero și îl vom schimba cu 0 și îl vom returna.
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 < sorted.length; i++){  if(sorted[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(''); }

Rularea programului

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 < sorted.length; i++){     if(sorted[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('');*/

Cum functioneaza

Am creat mai întâi matricea de caractere precum ['5', '5', '0', '1', 0] . Apoi vom rezolva asta['0', '0', '1', '5', '5'] După aceasta, găsim primul element diferit de zero și îl schimbăm cu primele elemente zero ca ['1', '0', '0', '5', '5'] . Acum avem cel mai mic număr gata, trebuie doar să le concatenăm împreună și să le returnăm.

ad-banner

Aflați mai multe despre Despică(), fel(), a te alatura().

Complexitatea timpului: O (nlogn).
Complexitatea spațială: O (n).

Explicarea complexității timpului și spațiului

Creăm o matrice de caractere care va dura O (n) timp. Apoi, sortarea matricei va lua O (nlogn).

După aceea, găsim indicele celui mai mic număr diferit de zero care poate lua O (n) în cel mai rău caz și unirea matricei pentru a crea șirul va lua O (n). Pe măsură ce toate aceste operații rulează una după alta. Deci complexitatea timpului este O (n + nlogn + n + n) = O (nlogn).

Creăm o serie de caractere din șir, deci complexitatea spațiului este O (n).

Folosind valoarea numerică O (logn).

Există un dezavantaj în această abordare: dacă numărul conține doar zerouri, atunci va returna un singur zero.

Implementare

  • Vom crea o serie de numere de la 0 la 9.
  • Apoi vom urmări cifrele prezente în număr prin creșterea numărului lor în matrice.
  • După aceea, vom găsi cea mai mică cifră diferită de zero și îi vom reduce numărul cu 1.
  • În cele din urmă, vom recrea numărul aranjându-le în ordine crescătoare și vom returna rezultatul.
  • Această soluție se bazează pe sortarea numărării.
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; }

Rularea programului

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

Complexitatea timpului: O (nlogn).
Complexitatea spațială: O (1).

Explicarea complexității timpului și spațiului

Eliminăm fiecare cifră din număr și incrementăm numărul său respectiv într-o matrice care va lua O (logn). Apoi găsim cel mai mic număr diferit de zero din matricea din O (10).

După aceea, rearanjăm cifrele pentru a crea cel mai mic număr în O (10 * logn). Complexitatea timpului este O (logn + 10+ 10logn) = O (logn) sau O (d), unde d este numărul de cifre

Folosim spațiu constant (o matrice de 10 numere), deci complexitatea spațiului este O (1).

Dacă ți-a plăcut acest articol, te rog dă-i câteva? Și împărtășește-l! Dacă aveți întrebări legate de acest lucru, nu ezitați să mă întrebați.

Pentru mai multe astfel de soluții și soluții algoritmice în Javascript, urmați-mă Stare de nervozitate. Scriu despre ES6, React, Nodejs, Structuri de date, și Algoritmi pe learnersbucket.com.