我有一個整數串列。數字可以重復。我希望以這種方式“排序”它們以獲得盡可能多的“跳躍”（從下一個元素到當前元素的差異是積極的）。
例子：
[10, 10, 10, 20, 20, 20] # only one "jump" from 10 to 20
[10, 20, 10, 20, 10, 20] # three jumps (10->20, 10->20, 10->20) - the correct answer
[20, 10, 20, 10, 20, 10] # two jumps
[11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11] # 9
[9, 11, 2, 19, 4, 11, 15, 5, 7, 11, 16, 19, 1, 4, 8, 11, 16, 19, 9, 17] # 14
[2, 9, 11, 16, 17, 19, 4, 5, 8, 15, 16, 9, 11, 1, 7, 11, 19, 4, 11, 19] # 15
[1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11] # 16
我完全低效（但有效）的代碼。：
def sol1(my_list):
my_list.sort()
final_list = []
to_delete = []
i = 0
last_element = float('-inf')
while my_list:
if i >= len(my_list):
i = 0
for index in to_delete[::-1]:
my_list.pop(index)
if len(my_list):
last_element = my_list.pop(0)
final_list.append(last_element)
to_delete = []
continue
curr_element = my_list[i]
if curr_element > last_element:
final_list.append(curr_element)
last_element = curr_element
to_delete.append(i)
i = 1
return final_list
有誰知道優化解決方案的方法？現在我正在多次迭代串列。它不需要在 Python 中。
uj5u.com熱心網友回復：
該演算法應處理重復值，以便首先所有第一次出現的數字按排序順序出現，然后第二次出現的重復值按排序順序出現，然后是第三次出現，......等等。
from collections import Counter
lst = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
result = [num for _,num in sorted(
(i, num)
for num, freq in Counter(lst).items()
for i in range(freq)
)]
result將會：
[1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11]
uj5u.com熱心網友回復：
我認為這應該是等效的，只需要 O(n log n) 時間進行排序，其余時間 O(n) 時間。尚未徹底測驗/基準測驗（現在沒有時間，我只是在打電話）。
from collections import Counter, OrderedDict
arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
d = OrderedDict(Counter(sorted(arr)))
ans = []
while d:
ans = d
for x in list(d):
d[x] -= 1
if not d[x]:
del d[x]
print(ans)
另一個，靈感來自 trincot：
from collections import defaultdict
from itertools import count
arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
d = defaultdict(count)
arr.sort(key=lambda x: (next(d[x]), x))
print(arr)
uj5u.com熱心網友回復：
cumcount根據之前出現的次數給出每個元素。然后先按cumcount其值排序。
arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
cumcount = []
d = dict.fromkeys(arr, 0)
for el in arr:
cumcount.append(d[el])
d[el] = 1
[x[1] for x in sorted(zip(cumcount, arr))]
# [1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/479027.html