Як сформувати якнайменше число з даного числа в JavaScript

У цьому посібнику ми реалізуємо алгоритм формування якнайменшого числа за допомогою ES6.

Input: 55010 7652634
Output: 10055 2345667

Примітка : Перетворене число не повинно починатися з 0, якщо воно має принаймні один ненульовий символ.

Для вирішення цієї проблеми ми будемо використовувати два різні підходи. Все буде написано на ES6.

  • У першому підході ми припустимо, що надане число має формат рядків, і вирішимо його, використовуючи сортування, яке займе O (nlogn).
  • У другому підході ми будемо вирішувати з числовим значенням з O (d) часом, де d - кількість цифр.

Використання сортування O (nlogn).

Впровадження

  • Ми перетворимо число в масив символів, а потім відсортуємо цей масив.
  • Після сортування ми перевіримо, чи є перший символ у масиві 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']. Тепер у нас є наше найменше число, нам просто потрібно об’єднати їх разом і повернути.

Дізнайтеся більше про split (), sort (), join ().

Складність часу: O (nlogn).

Складність простору: O (n).

Пояснення складності часу та простору

Ми створюємо масив символів, який займе O (n) часу. Тоді сортування масиву займе O (nlogn).

Після цього ми знаходимо індекс найменшого ненульового числа, яке може приймати O (n) у гіршому випадку, і приєднання масиву для створення рядка займе O (n). Оскільки всі ці операції виконуються одна за одною. Тож складність часу дорівнює O (n + nlogn + n + n) = O (nlogn).

Ми створюємо масив символів із рядка, тому складність простору дорівнює O (n).

Використовуючи числове значення O (logn).

У цьому підході є недолік: якщо число містить лише нулі, воно поверне одиничний нуль.

Впровадження

  • Ми створимо масив чисел від 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*/

Складність часу: O (nlogn).

Складність простору: O (1).

Пояснення складності часу та простору

Ми видаляємо кожну цифру з числа та збільшуємо відповідний відлік у масиві, який прийме O (logn). Тоді ми знаходимо найменше ненульове число з масиву в O (10).

Після цього ми переставляємо цифри, щоб створити найменше число в O (10 * logn). Складність часу становить O (logn + 10+ 10logn) = O (logn) або O (d), де d - число цифр

Ми використовуємо постійний простір (масив із 10 чисел), тому складність простору дорівнює O (1).

Якщо вам сподобалась ця стаття, дайте, будь ласка, і поділіться нею! Якщо у вас є якісь питання, пов’язані з цим, сміливо задавайте мені.

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.