按频率递减排序，不重复，以o(n)为单位。

Question

我有一个范围为{1......n}的整数数组，我需要给出一个O(n)算法，它可以去掉重复的数字，并对数组中的元素进行频率递减排序，从出现最多的元素开始。

我想过用radix sort或某个版本的计数排序，但不知道如何在o(n)中实现。感谢你的帮助。

Answer 1

有几种方法，一种可能的解决方案。

首先，对所有元素进行计数（计数排序的第一步），然后创建一个直方图，其中： count[i] = #times i appeared. 这就是 O(n).

然后，创建第二个数组 (frequency, i) 在删除所有重复的内容后。这就是 O(n).

最后，对新的数组进行计数排序，按频率进行比较，然后输出数值。这就是 O(n).