Maximum number that can be formed from the given d

问题:

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

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

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

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).

Example:

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.

回答1:

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

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.