数组中第 K 大的元素(剑指 Offer II 076)
哪些公司问过
答案要点
- 排序法 O(n log n),第 k 大即升序下标 n-k
- 小顶堆维护 k 个最大元素,堆顶即答案,O(n log k),适合流式数据
- 快速选择基于分区,只递归目标一侧,平均 O(n)、最坏 O(n²)
- 随机选基准避免最坏情况,大量重复元素可用三路划分
- 注意 k 与下标的换算,第 k 大对应升序位置 n-k
易错点
- 把第 k 大误算成升序下标 k-1
- 快速选择固定取第一个元素作基准,遇到有序数组退化到 O(n²)
- 用大顶堆存全部元素再弹 k 次,空间 O(n) 却以为更优
面试官常见追问
- 如果是海量数据,内存放不下怎么办?
- 快速选择为什么平均是 O(n)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。