找到由给定数字的数字组成的最大可能数字

Question

给定数字N找到可以从给定数字数字创建的最大可能数字X.

实施例：N = 231，则X将是321

的限制是时间复杂度O（1） 和空间复杂度O（1）。

我认为这必须通过计数排序来完成。

Answer 1

我能做的最好的是O（1）空间和O（log（N））时间。很确定不可能做得更好，因为在最低限度内，您必须分析输入中的每个数字，即log（N）。

简短的回答是，按降序对N的数字进行排序。

伪代码：

1. 创建的10个整数的数组，全部初始化为0。
2. 遍历N的每个数字。增加阵列中与每个数字对应的插槽。
3. 遍历数组。将字符C的N个实例添加到结果字符串的开头，其中N是数组中存储在插槽编号C中的编号。

样品Python实现：

N = 231 
slots = [0,0,0,0,0,0,0,0,0,0] 
while N > 0: 
    slots[N%10] += 1 
    N = int(N/10) 

result = "" 
for slot_idx in range(10): 
    for i in range(slots[slot_idx]): 
     result = str(slot_idx) + result 

print result 

结果：