Како у ЈаваСцрипт формирати најмањи могући број из датог броја

У овом упутству ћемо применити алгоритам за формирање најмањег могућег броја помоћу ЕС6.

Input: 55010 7652634
Output: 10055 2345667

Напомена : Трансформисани број не би требало да започиње са 0 ако има бар један знак који није нула.

За решавање овог проблема користићемо два различита приступа. Све ће бити написано у ЕС6.

  • У првом приступу, претпоставићемо да је наведени број у формату низа и решити га помоћу сортирања за које је потребно О (нлогн).
  • У Другом приступу решаваћемо нумеричком вредношћу са временом О (д), где је д број цифара.

Коришћење сортирања О (нлогн).

Имплементација

  • Број ћемо претворити у низ знакова, а затим сортирати тај низ.
  • Након сортирања проверићемо да ли је први знак у низу 0.
  • Ако није 0, придружићемо се низу и вратити га.
  • Ако је 0, пронаћи ћемо први број који није нула и заменити га са 0 и вратити.
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(''); }

Покретање програма

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

Како то ради

Прво смо створили низ знакова попут ['5', '5', '0', '1', 0]. Затим ово сортирамо на ['0', '0', '1', '5', '5']После овога, проналазимо први нула елемент и замењујемо га са првих нула елемената попут ['1', '0', '0', '5', '5']. Сада имамо свој најмањи број спреман, само их треба спојити и вратити.

Сазнајте више о сплит (), сорт (), јоин ().

Сложеност времена: О (нлогн).

Сложеност простора: О (н).

Објашњење сложености времена и простора

Стварамо низ знакова за који је потребно О (н) време. Тада ће сортирање низа трајати О (нлогн).

Након тога, налазимо индекс најмањег нултог броја који може узети О (н) у најгорем случају, а спајање низа за стварање низа узимаће О (н). Како се све ове операције изводе једна за другом. Дакле, временска сложеност је О (н + нлогн + н + н) = О (нлогн).

Стварамо низ знакова из низа, тако да је сложеност простора О (н).

Коришћење нумеричке вредности О (логн).

У овом приступу постоји недостатак: ако број садржи само нуле, он ће вратити једну нулу.

Имплементација

  • Створићемо низ бројева од 0 до 9.
  • Тада ћемо пратити цифре присутне у броју повећавајући њихов број у низу.
  • После тога ћемо пронаћи најмању цифру која није нула и смањити њен број за 1.
  • На крају ћемо поново створити број тако што ћемо их поређати у растућем редоследу и вратити резултат.
  • Ово решење се заснива на сортирању бројача.
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; }

Покретање програма

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

Сложеност времена: О (нлогн).

Сложеност простора: О (1).

Објашњење сложености времена и простора

Уклањамо сваку цифру из броја и повећавамо њено бројање у низу који ће имати О (логн). Тада проналазимо најмањи не-нулти број из низа у О (10).

После тога преуређујемо цифре да бисмо створили најмањи број у О (10 * пријава). Сложеност времена је О (логн + 10+ 10логн) = О (логн) или О (д), где је д број цифара

Користимо константни размак (низ од 10 бројева), тако да је сложеност простора О (1).

Ако вам се свидео овај чланак, дајте га мало и поделите га! Ако имате питања у вези са овим, слободно ме поставите.

За више сличних овоме и алгоритамска решења у Јавасцрипту, следите ме на Твиттер-у . Пишем о ЕС6, Реацт, Нодејс, структурама података и алгоритмима на Леарнерсбуцкет.цом .