TopK 问题的解法
哪些公司问过
答案要点
- 排序法:O(n log n),实现最简单,数据量大时不划算
- 堆法:找最大 K 个用大小为 K 的小顶堆,比堆顶大就替换;O(n log K),空间 O(K),适合海量和流式数据
- 快速选择:基于 partition,平均 O(n)、原地;最坏 O(n²),用随机 pivot 或三数取中缓解
- 频率 TopK:哈希表统计频率,再用堆或桶排序取前 K
- C++ 可直接用 nth_element(introselect),priority_queue 实现堆
易错点
- 找最大 K 个却用大顶堆,空间变成 O(n)
- 快速选择不处理重复元素,导致退化
- 只会排序,说不出海量数据的做法
- 混淆第 K 大和前 K 大
面试官常见追问
- 为什么找最大的 K 个要用小顶堆?
- 一亿个 int 大约占多少内存,放不进内存怎么办?
- 流式数据怎么求第 N 大?
- 1TB 的文件、128GB 内存,怎么求最大的 10 个数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。