给定一个包含可能重复条目的数组 A,找到出现频率最高的 k 个条目。
我的方法:
创建一个按频率排序的 k 个最常出现的元素的 MinHeap。顶部元素显然是其余元素中出现最少的。 创建一个 HashMap 来跟踪所有元素计数以及它们是否在 MinHeap 中。
当读取一个新的整数时:
- 检查是否在HashMap中:增加HashMap中的计数
- 同时检查它是否在堆中:然后增加那里的计数并堆化。
- 如果不是,则与根元素计数进行比较,并在必要时删除根元素以添加它。然后堆化。
最后返回 MinHeap 作为期望的输出。
class Wrapper{
boolean inHeap;
int count;
}
这需要 O(n+k) 空间和 O(n log k) 时间复杂度。有没有更好的方法来明智地处理空间和/或时间复杂度。
最佳答案
我们可以说您的方法的空间复杂度为 O(n)
,因为您永远不会使用超过 O(2n) = O(n)
的内存。
跳过堆,只创建 HashMap。
创建 HashMap 后,您可以遍历它并将所有元素放入一个数组中。
然后你可以运行 selection algorithm例如quickselect在数组上获取第 k
元素,以及第一个 k
元素(通过 quickselect 提取第一个 k
元素的扩展是相当微不足道,或者您可以再次迭代以获取它们)。
然后根据需要对 k
元素进行排序。
如果需要排序,预计运行时间为 O(n)
或 O(n + k log k)
。
空间复杂度为 O(n)
。
关于java - 在整数数组中找到 k 个出现次数最多的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24027482/