给你一个整数数组,你可以根据
它们的发生。设计算法并分析其时间复杂度。如果系上较小的
编号应该出现在排序列表的第一位。
样本输入:3,4,3,2,3,5,4,2,2,1,2
样本输出:1 5 4 3 2
最佳答案
如果允许额外的空间:检查输入并进行频率分析把它写在哈希表里。这大致意味着:
for each x in input:
if x in table:
++table[x]
else
table.insert(x)
然后,对唯一值进行简单的快速排序,比较函数将频率而不是值本身考虑在内。
即:
function freq_compare (x, y):
return compare(table[x], table[y])
其中
compare
是频率的数字。关于algorithm - 基于频率的排序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/1811671/