给定一个整数，发现可以从数字地形成的最大数量。 输入：8754365 输出：8765543

Given a Integer, find the maximum number that can be formed from the digits. Input : 8754365 output : 8765543

我说，在$为O（n LOGN）$的解决方案。他问我进一步优化。

I told solution in $O(n logn)$. He asked me optimize further.

我们可以使用哈希表来进一步优化，$ \ RIGHTARROW $ O（N）

We can use Hash Table to optimize further, $\rightarrow$ O(n)

算法： 1.取一个哈希表大小为10（0〜9）。 2.存储每一位的从0到9的计数。 3.打印哈希表的索引相对于位数计数在反​​方向（从9到0）。

Algorithm: 1. Take a hash table with size 10 (0 to 9). 2. Store the count of every digit from 0 to 9. 3. Print the index of the Hash table with respect to digit count in the reverse direction (from 9 to 0).

例如：

哈希表后的数字计数8754365 $ \ RIGHTARROW $（0 0 0 1 1 2 1 1 1 0） 打印哈希表的索引相对于它们的计数相反顺序$ \ RIGHTARROW $ 8765543 时间复杂度：O（N） 纠正我，如果我错了。

Hash table after digit count for 8754365 $\rightarrow$ (0 0 0 1 1 2 1 1 1 0) Print the index of the hash table with respect to their count in reverse order $\rightarrow$ 8765543 Time Complexity : O(n) Correct me if I am wrong.

推荐答案

下面的贪婪 code 做这在O（n）时间。其中n是在号码的位数。

The following greedy code does this in O(n) time. Where n is the number of digits in the number.

int num = 8756404;
int[] times = new int[10];
while(true){
    if(num==0){
        break;
    }
    int val = num%10;
    times[val]++;
    num /= 10;
}
for(int i=9; i>=0; i--){
    for(int j=0; j<times[i]; j++){
        System.out.print(i);
    }
}

它通过计数每个在输入号码数字的出现的次数。然后打印的每个号码的次数它是在以相反的顺序输入的号码，即从9日开始至0。

It works by counting the number of occurences of each of the digits in the input number. Then printing each number the number of times it was in the input number in reverse order, ie. starting from 9 to 0.