找到由給定數字的數字組成的最大可能數字

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 

結果：