参考答案
内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 29 天前更新
小顶堆做法
- 维护一个大小为 k 的小顶堆:遍历数组,堆未满直接入堆;堆满后,若当前元素大于堆顶,弹出堆顶并插入当前元素。
- 遍历结束,堆中就是最大的 k 个元素,堆顶是第 k 大。
- 时间复杂度 O(n log k),空间 O(k);适合 n 很大、k 较小,或数据流/在线场景。
快速选择(Quickselect)
- 用快排的 partition 找第 k 大,平均 O(n),最坏 O(n²)(可通过随机 pivot/三数取中缓解);原地、空间 O(1)。
- 适合一次性离线数据、内存放得下、对最坏情况可接受或能做随机化;不稳定,不保证输出顺序。
怎么选
- k << n 或流式:小顶堆;n 中等且追求平均性能:快速选择;要求稳定顺序/多次查询:排序或维护有序结构;数据量超大:分治/外部排序 + 堆。
- 注意“第 k 大”和“前 k 大”的边界;有重复元素时明确是否去重;Java 可用
PriorityQueue,C++ 用 priority_queue 默认大顶堆,需要自定义比较器。
代码要点
import heapq
def topk(nums, k):
h = []
for x in nums:
if len(h) < k: heapq.heappush(h, x)
elif x > h[0]: heapq.heapreplace(h, x)
return h
常见坑
- 用大顶堆存全部再取 k 个,复杂度 O(n log n);k 大于 n;堆比较器写反;快速选择递归边界写错。