by Prashant Yadav

通过Prashant Yadav

如何从JavaScript中的给定数字中形成最小的数字 (How to form the smallest possible number from a given number in JavaScript)

In this tutorial, we will implement an algorithm to form the smallest possible number with ES6.

在本教程中，我们将实现一种算法，以使用ES6形成尽可能小的数字。

Input: 55010 7652634

Output: 10055 2345667

Note: The transformed number should not start with 0 if it has at least one non-zero character.

注意：如果转换后的数字至少包含一个非零字符，则不应以0开头。

We are going to use two different approaches to solve this problem. Everything will be written in ES6.

我们将使用两种不同的方法来解决此问题。一切都将用ES6编写。

In the first approach, we will assume that the provided number is in string format and solve it using sorting which will take O(nlogn).
在第一种方法中，我们将假定提供的数字为字符串格式，并使用将采用O(nlogn)的排序对其进行求解。
In the Second approach, we will solve with numeric value with O(d) time, where d is the number of digits.
在第二种方法中，我们将使用O(d)时间的数值进行求解，其中d是位数。

使用排序O(nlogn)。 (Using sorting O(nlogn).)

实作 (Implementation)

We will convert the number to the character array and then sort that array.
我们将数字转换为字符数组，然后对该数组进行排序。
After sorting we will check if the first character in the array is 0.
排序后，我们将检查数组中的第一个字符是否为0。
If it is not 0 then we will join the array and return it.
如果它不是0，那么我们将加入数组并返回它。
If it is 0 then we will find the first non-zero number and swap it with 0 and return it.
如果它是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 < 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(''); }

Running the Program

运行程序

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

这个怎么运作 (How it works)

We first created the array of characters like ['5', '5', '0', '1', 0] . Then we sort this to['0', '0', '1', '5', '5'] After this, we find the first non-zero element and swap it with first zero elements like ['1', '0', '0', '5', '5'] . Now we have our smallest number ready we just need to concatenate them together and return it.

我们首先创建了一个字符数组，例如['5', '5', '0', '1', 0] 。然后，将其排序为['0', '0', '1', '5', '5']之后，我们找到第一个非零元素并将其与诸如['1', '0', '0', '5', '5'] 。现在我们已经准备好最小的数目，我们只需要将它们连接在一起并返回即可。

Learn more about the split(), sort(), join().

了解有关split() ， sort() ， join()的更多信息。

Time Complexity: O(nlogn).Space Complexity: O(n).

时间复杂度：O(nlogn)。空间复杂度：O(n)。

时空复杂度说明 (Time and Space complexity explanation)

We are creating a character array which will take O(n) time. Then sorting the array will take O(nlogn).

我们正在创建一个需要O(n)时间的字符数组。然后对数组排序将使用O(nlogn)。

After that, we are finding the index of smallest non zero number which can take O(n) in the worst case and joining the array to create the string will take O(n). As these all operations are running one after other. So time complexity is O(n + nlogn + n + n) = O(nlogn).

此后，我们找到最小的非零数字的索引，该索引在最坏的情况下可以采用O(n)，并加入数组以创建字符串将采用O(n)。由于所有这些操作都在一个接一个地运行。因此，时间复杂度为O(n + nlogn + n + n)= O(nlogn)。

We are creating an array of characters from the string, so space complexity is O(n).

我们正在根据字符串创建字符数组，因此空间复杂度为O(n)。

使用数值O(logn)。 (Using numeric value O(logn).)

There is a drawback in this approach: if the number only contains zeros then it will return a single zero.

这种方法有一个缺点：如果数字仅包含零，则它将返回单个零。

实作 (Implementation)

We will create an array of numbers from 0 to 9.
我们将创建一个从0到9的数字数组。
Then we will keep track of the digits present in the number by increasing their count in the array.
然后，我们将通过增加数组中的数字来跟踪数字中存在的数字。
After that, we will find the smallest non-zero digit and decrease its count by 1.
之后，我们将找到最小的非零数字并将其计数减少1。
In the end, we will recreate the number by arranging them in ascending order and return the result.
最后，我们将按升序排列数字，然后返回结果。
This solution is based on the counting sort.
该解决方案基于计数排序。

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; }

Running the program

运行程序

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

Time Complexity: O(nlogn).Space Complexity: O(1).

时间复杂度：O(nlogn);空间复杂度：O(1)。

时空复杂度说明 (Time and Space complexity explanation)

We are removing each digit from the number and incrementing its respective count in an array that will take O(logn). Then we find the smallest non-zero number from the array in O(10).

我们正在从数字中删除每个数字，并在需要O(logn)的数组中增加其各自的计数。然后我们从O(10)中的数组中找到最小的非零数。

After that we are rearranging the digits to create the smallest number in O(10 * logn). Time complexity is O(logn + 10+ 10logn) = O(logn) or O(d), where d is the no of digits

之后，我们将重新排列数字以在O(10 * logn)中创建最小的数字。时间复杂度为O(logn + 10+ 10logn)= O(logn)或O(d)，其中d为数字位数

We are using constant space (an array of 10 numbers), so space complexity is O(1).

我们使用的是恒定空间(由10个数字组成的数组)，因此空间复杂度为O(1)。

If you liked this article, please give it some ?and share it! If you have any questions related to this feel free to ask me.

如果您喜欢这篇文章，请给它一些？并分享！如果您对此有任何疑问，请随时问我。

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.

有关Java的更多此类信息和算法解决方案，请在 Twitter上 关注我 。我写ES6 ，React过来，的NodeJS，数据结构和算法上learnersbucket.com 。