LeetCode 215. 数组中的第K个最大元素
题目描述
题意分析
要找的是数组按从大到小排列后的第
k个元素，重复值按出现次数分别占据名次，不能先去重。题目保证数组非空，且1 <= k <= n，因此答案一定存在。排序后取值可以得到答案，但会确定所有元素的顺序，而题目只关心一个位置。把问题转成升序下标后，前面有
n - k个元素的位置就是第k大，即target = n - k。两种思路都可以避免完整排序：小顶堆只保留最大的
k个候选，快速选择只继续处理包含目标下标的区间。小顶堆便于理解和处理持续到来的数据，但不满足题目线性时间的要求；随机快速选择的期望时间为 $O(n)$，最坏时间仍可能达到 $O(n^2)$。
解法一：小顶堆
核心思路
[!blue]
只需要知道最大的
k个元素中最小的是谁：这个数前面恰好可以排下另外k - 1个保留元素，所以它就是第k大。为方便淘汰较小的候选，用小顶堆把当前保留元素的最小值放在堆顶。遍历时先把当前值加入堆。如果元素数量超过
k，就弹出堆顶，留下其中最大的k个。处理不足k个元素时全部保留，达到k个后，堆中始终保存已遍历部分最大的k个元素。为什么已经淘汰的值不需要再考虑？它被淘汰时，至少已有
k个保留元素不小于它；后续加入新元素只可能把这些候选替换成更大的值，不会使它重新成为必须保留的元素。遍历结束后，堆顶就是整个数组的第k大，重复值也会作为独立元素参与比较和保留。
解题步骤
- 创建一个空的小顶堆。
- 遍历数组，将当前元素加入堆。
- 如果堆中元素超过
k个，弹出堆顶，淘汰当前最小值。- 遍历结束，返回堆顶。
代码实现
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int num : nums) {
heap.offer(num);
// 多于名额时淘汰最小值，堆中只保留最大的 k 次出现。
if (heap.size() > k) {
heap.poll();
}
}
return heap.peek();
}
}
import "container/heap"
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func findKthLargest(nums []int, k int) int {
h := &MinHeap{}
for _, num := range nums {
heap.Push(h, num)
// 多于名额时淘汰最小值，堆中只保留最大的 k 次出现。
if h.Len() > k {
heap.Pop(h)
}
}
return (*h)[0]
}
复杂度分析
- 时间复杂度：$O(n \log k)$，每个元素入堆一次，堆大小最多为
k + 1；k = 1时为 $O(n)$。- 空间复杂度：$O(k)$，用于保存堆中的元素。
关键点总结
[!green]
- 保留最大的
k个，淘汰最小的：因此使用小顶堆，堆顶就是保留集合中排名最后的元素。- 重复值分别入堆：排名按元素个数计算，不能把堆替换成去重集合。
- Go 的
Pop返回末尾元素：heap.Pop(h)会先把堆顶换到末尾并调整堆，再调用自定义的Pop；不要在该方法里直接删除下标0。
解法二：三路分区快速选择
核心思路
[!blue]
快速选择借用快速排序的分区，但只处理答案所在的一侧。若当前区间已经分成“小于基准、等于基准、大于基准”三段，那么左段的所有值都不大于中段，中段的所有值都不大于右段；各段内部是否有序，不影响目标下标落在哪一段。
在当前区间
[left, right]随机选一个值作为pivot。用lt、i、gt维护四个范围：[left, lt)小于基准，[lt, i)等于基准，[i, gt]尚未检查，(gt, right]大于基准。开始时没有已分类的元素，整个区间都待检查。当前值小于基准时，把它与
lt交换，让它进入左段，再同时推进lt和i。当lt < i时，换回来的值原本就在等值段中，已经确定等于基准；当两者相等时只是原地交换，因此这两种情况都不需要重新检查当前位置。当前值大于基准时，把它与
gt交换，再缩小gt，让这个较大值进入右段。此时从右侧换回来的值尚未检查，所以i必须停在原地。当前值等于基准时，直接推进i，把它纳入等值段。每一步都会使待检查区间减少一个元素。当
i > gt，所有元素都已分类，等值段正好是[lt, gt]。如果target落在其中，这些位置的值都等于pivot，可以直接返回；如果target < lt，答案只可能在左段；如果target > gt，答案只可能在右段。保留下来的区间始终包含目标下标，其他区间无需继续排序。基准值取自当前区间，等值段一定非空，所以每次未命中时都能严格缩小范围。用三路分区一次跳过所有等于基准的元素，也避免了大量重复值被一轮轮单独处理；随机选择基准则降低了连续出现极不均衡划分的概率。
解题步骤
- 计算升序目标下标
target = n - k，初始化left = 0、right = n - 1。- 从
[left, right]随机选取并保存基准值，初始化lt = left、i = left、gt = right。- 当
i <= gt时，按当前值与基准的大小关系执行交换和移动，直到待检查区间为空。- 若
target < lt，令right = lt - 1；若target > gt，令left = gt + 1，重新对保留区间分区。- 若
lt <= target <= gt，返回nums[target]。target始终是原数组中的绝对下标，缩小区间后不需要重新计算。
代码实现
class Solution {
public int findKthLargest(int[] nums, int k) {
// 统一成升序目标下标，重复值仍分别占据名次。
int target = nums.length - k;
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int pivot =
nums[java.util.concurrent.ThreadLocalRandom.current().nextInt(left, right + 1)];
int lt = left;
int i = left;
int gt = right;
while (i <= gt) {
if (nums[i] < pivot) {
swap(nums, lt++, i++);
} else if (nums[i] > pivot) {
// 右侧换回的值还未分类，本轮不能推进 i。
swap(nums, i, gt--);
} else {
i++;
}
}
// 只继续包含目标的区间，等值段命中时即可直接返回。
if (target < lt) {
right = lt - 1;
} else if (target > gt) {
left = gt + 1;
} else {
return nums[target];
}
}
throw new IllegalStateException();
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
import "math/rand"
func findKthLargest(nums []int, k int) int {
// 统一成升序目标下标，重复值仍分别占据名次。
target := len(nums) - k
left, right := 0, len(nums)-1
for left <= right {
pivot := nums[left+rand.Intn(right-left+1)]
lt, i, gt := left, left, right
for i <= gt {
if nums[i] < pivot {
nums[lt], nums[i] = nums[i], nums[lt]
lt++
i++
} else if nums[i] > pivot {
// 右侧换回的值还未分类，本轮不能推进 i。
nums[i], nums[gt] = nums[gt], nums[i]
gt--
} else {
i++
}
}
// 只继续包含目标的区间，等值段命中时即可直接返回。
if target < lt {
right = lt - 1
} else if target > gt {
left = gt + 1
} else {
return nums[target]
}
}
panic("unreachable")
}
复杂度分析
- 时间复杂度：期望 $O(n)$，单次分区只扫描当前区间，之后仅保留一侧；随机基准使剩余规模在期望意义下持续缩小，各轮扫描量的期望总和为线性量级。若连续选到极端基准，每次仅减少少量元素，最坏仍为 $O(n^2)$。
- 空间复杂度：$O(1)$，在原数组中交换元素，并通过循环缩小区间，不使用递归栈。
关键点总结
[!green]
- 下标统一用升序：第
1大对应n - 1，第n大对应0，因此目标下标始终是n - k。- 只保留一侧：分区后另一侧不可能包含目标，无需继续排序；等值段覆盖目标时可立即结束。
- 重复值不单独递归处理：全相等数组经过一轮分区即可返回。随机基准改善划分的期望表现，但不消除最坏情况。
易错点总结
[!yellow]
- 堆的方向不能写反：大小为
k的小顶堆保留最大的k个数；同样大小的大顶堆会保留最小的k个数。- 目标下标不能混用：快速选择按升序分区，第
k大对应n - k；k - 1是降序排列的下标，不能套入这里。- 不能去重：每次出现都占一个名次，去重会改变第
k大的含义。- 与右侧交换后不能递增
i：从gt换来的元素还没有检查，必须留在当前位置继续判断。- 基准要保存为值：分区会不断交换元素，不能一边交换一边从最初的基准下标重新读取。
- 区间更新要排除等值段：使用
lt - 1和gt + 1，避免重复处理已经确定的部分；该实现会改变原数组顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 703. 数据流中的第 K 大元素 | 简单 | 原题持续加入数据并查询第k大，本题只做一次选择，可用快速选择或堆。 |
| 347. 前 K 个高频元素 | 中等 | 同样挑选TopK，原题排名依据为元素频次，本题依据数值大小。 |
| 692. 前K个高频单词 | 中等 | 用大小受限的堆保留排名靠前的候选；本题以数值为排序依据选择第 k 大，该题以单词频次和字典序联合排序。 |
| 973. 最接近原点的 K 个点 | 中等 | 用大小受限的堆保留排名靠前的候选；本题以数值为排序依据选择第 k 大，该题以到原点的平方距离为排序依据。 |