TOP-K问题解法#
一句话答案#
Top-K 三种解法：快速选择 O(n) 平均、小顶堆 O(nlogk) 适合流式、排序 O(nlogn) 最简单。
核心要点
| 方法 | 时间 | 空间 | 适用 |
|---|---|---|---|
| 快速选择 | O(n) | O(1) | 一次性大数据 |
| 小顶堆 | O(nlogk) | O(k) | 流式/动态 |
| 排序 | O(nlogn) | O(1) | 数据量小 |
小顶堆： 维护 K 大小的堆，遍历时比堆顶大就替换
快速选择为什么平均 O(n)#
与快排的区别： 快排 partition 后两边都递归；快速选择只需第 K 大，partition 后只有一边含目标，只递归一边，另一边整块丢弃。
平均代价递推： 随机 pivot 下，每次 partition 是 O(n)，期望把规模砍掉常数比例（理想取一半）：
展开为等比级数： 每层只做一段、规模逐层减半：
对比快排
T(n)=2T(n/2)+O(n)每层都是满 n、共 logn 层 → O(nlogn)。快速选择因为只走一条链，各层规模等比衰减、收敛到 2n，所以是线性而非 nlogn。
最坏 O(n²)： pivot 每次取到极值（如有序数据取首元素），规模只减 1，退化成 n+(n-1)+…=O(n²)。随机化 pivot 使其概率极低；要硬保证最坏 O(n) 用 BFPRT（中位数的中位数），但常数大、实践少用。
面试回答（2分钟版）
Top-K问题有三种经典解法。第一种是小顶堆，维护一个大小为K的小顶堆，堆顶是当前K个最大值中最小的那个相当于门槛，遍历数据时比堆顶大就替换进来，遍历完堆里就是最大的K个元素，时间O(nlogk)空间O(k)，最大优势是支持流式数据和动态场景。第二种是快速选择算法，思路类似快排但每次只递归一半：做一次partition后如果pivot位置正好是第K个就结束，pivot靠左就递归右半边，靠右就递归左半边，平均时间O(n)空间O(1)，适合一次性大数据量场景，但最坏情况O(n^2)可以通过随机选pivot优化。第三种是直接排序取前K个，时间O(nlogn)最简单但效率最低，只适合数据量小的情况。一个反直觉的点是找最大的K个数要用小顶堆而不是大顶堆，因为小顶堆堆顶是门槛，比门槛高的才能进来替换最小的。海量数据场景下可以先用哈希分片到多台机器，每台机器求局部TopK，最后合并各机器的结果。
追问与易错
追问方向：
- “快速选择的最坏情况怎么优化？”→ 随机化 pivot 避免有序数据退化到 O(n^2)；更严格可用 BFPRT（中位数的中位数）算法保证最坏 O(n)，但常数大实际较少使用
- “快速选择平均 O(n) 怎么推？”→ 只递归含目标的一边，递推 T(n)=T(n/2)+O(n)，逐层展开 n+n/2+n/4+…=2n 等比收敛，故 O(n)；对比快排 T(n)=2T(n/2)+O(n) 两边都递归、每层满 n 共 logn 层 → O(nlogn)
- “Top-K 的 K 很大怎么办？”→ K 接近 n 时堆方法优势不明显，可转化为求 Top-(n-K) 最小再取补集；或直接用快速选择 O(n) 平均复杂度，不受 K 大小影响
- “海量数据 Top-K 怎么做？”→ 数据分片到多台机器各自求局部 Top-K，再汇总所有局部结果用小顶堆归并求全局 Top-K；单机内存不够时用外部排序或位图/布隆过滤器预筛
易错点：
- ❌ 排序是 Top-K 最好方案——堆方法 O(nlogk) 更优
- ❌ 小顶堆不是应该用大顶堆吗——Top-K 大用小顶堆