algorithm - 按出现频率的顺序打印列表唯一项目

Question

假设我们有一个整数数组，甚至是连续的整数流。这个想法是根据出现频率按降序打印唯一元素。例如，对于 7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1 我们应该得到: 2, 4, 6, 7, 9, 5, 0, 1 因为 2 出现了三个次，4 和 6 两次，其余仅一次。

有没有比(sorting map based by value)计算元素的出现次数，将它们存储在 map 中，然后根据值对 map 排序的更好和有效的方法？

Answer 1

However, it seems to me that there should be much effective algorithm for this, as probably there is a way for sorting frequencies on fly.

这个问题实际上是代数树模型中的Omega(nlogn)(该模型下不允许散列)，从 Element Distinctness Problem减少，所以如果您希望通过一次(或常数次)迭代来解决它，而不需要任何辅助数据结构来解决它 - 这是不可能的，因为它将允许我们解决元素的差异性代数树模型中的 O(n)。

这些类型问题的规范解决方案是:

1. (您的建议):构建 map 、删除重复项并按频率排序
2. 类似于 1，但不是映射 - 对项目进行排序，使用二分查找可以轻松找到每个元素重复的次数。