algorithm - 给定数字可以组成的最大数

Question

给定一个整数，找出可以由这些数字组成的最大数。输入:8754365输出:8765543

我在 $O(n logn)$ 中告诉了解决方案。他让我进一步优化。

我们可以使用Hash Table进一步优化，$\rightarrow$ O(n)

算法:1. 取一个大小为 10(0 到 9)的哈希表。2. 存储 0 到 9 的每一位数字的个数。3. 反方向(从9到0)打印Hash表的索引。

示例:

数字计数后的哈希表 8754365 $\rightarrow$ (0 0 0 1 1 2 1 1 1 0)以相反的顺序打印哈希表的索引与它们的计数 $\rightarrow$ 8765543时间复杂度:O(n)如果我错了，请纠正我。

Answer 1

下面贪心code在 O(n) 时间内完成。其中 n 是数字中的位数。

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。