数组中的第K个最大元素
Kth Largest Element in an Array
返回数组中第 k 大的元素（按大小排序后的第 k 个，不是第 k 个不同值）。
在力扣中练习题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
解题思路
小顶堆 · 保留最大的 k 个
堆里始终只有 k 个数，堆顶就是第 k 大
要找第 k 大，不需要把所有数排序。维护一个大小为 k 的小顶堆：
- 新元素直接入堆；
- 堆超过 k 个时，弹出堆顶（当前 k 个里最小的）；
- 扫描结束后，堆里正好是最大的 k 个，堆顶就是第 k 大。
维护一个大小为 4 的小顶堆：新元素入堆，超过 k 个就弹掉堆顶。
空树 · null
用小顶堆而不是大顶堆，是因为我们要淘汰“最大的 k 个里最小的那个”。若用大顶堆，堆顶是全局最大，反而无法判断谁该出局。
8 入堆，堆超过 4 个，弹掉最小的 2；当前堆顶 4。
- heap.size
- 4
自拟数组有两个 9，k=4：堆最终保留 [7,8,9,9]，堆顶 7 就是第 4 大。重复值不会影响堆的大小逻辑。
时间 O(n log k)，空间 O(k)。k 远小于 n 时比排序更省。
易错点
- 用大顶堆：堆顶是最大值，无法在超过 k 个时淘汰最小者。
- 先全部入堆再弹 n-k 次：复杂度接近 O(n log n)，没有利用 k。
- 把“第 k 大”理解成第 k 个不同值：重复元素要分别计数。
快速选择 · 平均 O(n)
像快排一样分区，只递归包含答案的那一侧
平均 O(n)，但最坏 O(n²)，且会修改数组；面试中要主动说明随机化或最坏情况。
快排的分区会把数组分成“小于等于 pivot”和“大于 pivot”两部分。设右段（含 pivot）有 count 个元素：
count == k：pivot 就是第 k 大；count > k：答案在右段，只递归右边；count < k：答案在左段，变成第k-count大。
每次只递归一侧，平均时间 O(n)。但如果每次 pivot 都选到端点，会退化成 O(n²)；工程上可以随机选 pivot 或打乱数组。
它比堆更快，但会修改输入，且最坏情况不稳定。
- 1以区间末尾为 pivot 分区。
- 2统计右段元素个数 count。
- 3count 与 k 比较，只递归一侧。
- 4命中时返回 pivot。
易错点
- 两边都递归：退化成快速排序，O(n log n)。
- count 的计算漏掉 pivot 本身：差 1。
- 不随机化且输入有序：最坏情况容易触发。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [7,2,9,4,8,1,5,9,3]，k = 4维护一个大小为 4 的小顶堆：新元素入堆，超过 k 个就弹掉堆顶。
空树 · null
查看 C++ 代码
延伸阅读
- “第 k 大”与“最大的 k 个”是两种不同输出：前者只要一个值，后者要一个集合。
- 堆适合流式数据；快速选择适合一次性、可修改的数组。