java - 在整数数组中找到 k 个出现次数最多的元素

Question

给定一个包含可能重复条目的数组 A，找到出现频率最高的 k 个条目。

我的方法:

创建一个按频率排序的 k 个最常出现的元素的 MinHeap。顶部元素显然是其余元素中出现最少的。创建一个 HashMap 来跟踪所有元素计数以及它们是否在 MinHeap 中。

当读取一个新的整数时:

• 检查是否在HashMap中:增加HashMap中的计数
• 同时检查它是否在堆中:然后增加那里的计数并堆化。
• 如果不是，则与根元素计数进行比较，并在必要时删除根元素以添加它。然后堆化。

最后返回 MinHeap 作为期望的输出。

class Wrapper{
 boolean inHeap;
 int count;
}

这需要 O(n+k) 空间和 O(n log k) 时间复杂度。有没有更好的方法来明智地处理空间和/或时间复杂度。

Answer 1

我们可以说您的方法的空间复杂度为 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)。