LeetCode LCR 076. 数组中的第 K 个最大元素
题目描述
题意分析
返回数组降序排列后第
k个位置上的值。相同值的每次出现都占一个名次，所以不能先去重；题目保证1 <= k <= nums.length。只求一个名次，无需排好整个数组。可以保存当前最大的
k个候选，也可以通过分区不断缩小目标所在范围。下面保留最小堆和三路快速选择两种实现，分别说明它们的状态与复杂度。
解法一：大小为 k 的最小堆
核心思路
[!blue]
如果始终保留已扫描元素中最大的
k个，扫描结束后，这些候选中最小的值就是第k大。因此使用最小堆，让堆顶直接暴露最容易被淘汰的那个候选。每读入一个元素，先入堆；若数量超过
k，再弹出堆顶。此前没有进入前k大的元素，已经有至少k个元素不小于它，加入新元素后也不需要重新考虑。新的候选只可能是旧堆中元素和新元素，从中删去最小者，便继续保留最大的k个。所以每轮结束后，堆中都恰好保存已扫描前缀中最大的
min(k,已扫描数量)个元素。重复值作为多次出现分别入堆，仍按次数占位。最终堆大小为k，读取堆顶就是答案。
解题步骤
- 建立空的最小堆。
- 遍历
nums，将当前值入堆；若堆大小大于k，弹出最小值。- 扫描结束后读取堆顶。
k == 1时堆始终保留当前最大值；k == n时最终保留全部元素，堆顶就是最小值。Go 的底层Pop方法删除切片末项，是因为container/heap已先将待弹出的堆顶换到末尾，再调用这个方法。
代码实现
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
// 堆中始终只保留当前最大的 k 个数，堆顶就是这 k 个数里最小的。
minHeap.poll();
}
}
return minHeap.peek();
}
}
import (
"container/heap"
)
type MinHeap []int
func (h MinHeap) Len() int {
return len(h)
}
func (h MinHeap) Less(i int, j int) bool {
return h[i] < h[j]
}
func (h MinHeap) Swap(i int, 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
last := old[len(old)-1]
*h = old[:len(old)-1]
return last
}
func findKthLargest(nums []int, k int) int {
minHeap := &MinHeap{}
heap.Init(minHeap)
for _, num := range nums {
heap.Push(minHeap, num)
if minHeap.Len() > k {
// 堆中始终只保留当前最大的 k 个数，堆顶就是这 k 个数里最小的。
heap.Pop(minHeap)
}
}
return (*minHeap)[0]
}
复杂度分析
- 时间复杂度：$O(n\log(k+1))$，每个元素入堆一次、最多弹出一次，堆大小最多为
k+1。- 空间复杂度：$O(k)$，只保存有限个候选，不修改输入数组。
关键点总结
[!green]
- 要保留最大的
k个，就让最小候选处在堆顶，便于超限时淘汰。- 不变量在每次插入及可能的删除完成后成立，不能只按已经扫描的元素个数猜堆内内容。
- 只需最终第
k大的值，不需要再将堆中元素排成有序数组。
解法二：三路分区快速选择
核心思路
[!blue]
按降序排名，第
k大对应下标target = k-1。分区只需确认目标应该在哪一段，不必整理其他段内部的顺序。在当前区间选择
pivot，用三个指针维护四个部分：[left,greater)大于基准，[greater,idx)等于基准，[idx,less]尚未检查，(less,right]小于基准。若
nums[idx] > pivot，与greater交换，将较大值放到左区，再同时推进greater和idx。两指针不同时，换回的是已检查的等值元素；两指针相同时只是原位交换，因此都可以继续前进。若
nums[idx] < pivot，与less交换，将较小值放到右区，再将less左移。换回的元素来自未知部分，还必须检查，所以idx不动。相等时则只推进idx，扩大等值区。每步都减少一个未知位置。分区结束后，
[greater,less]全部等于基准，左侧都更大、右侧都更小，所以中段恰好占据这些相等元素应有的降序排名范围。若
target < greater，只保留左段；若target > less，只保留右段；否则目标已在等值段中，返回该值。目标下标始终使用原数组的绝对下标，不随范围缩小而重新计算。基准来自当前区间，等值段一定非空，所以未命中时范围也必定缩短。
解题步骤
- 设置
target = k-1，初始待选择范围为整个数组。- 取当前中间位置的值为基准，初始化
greater = idx = left、less = right。- 在
idx <= less时，按大于、小于、等于基准执行对应交换与指针更新。- 根据目标与等值区间的位置关系，收缩到一侧，或直接返回答案。
三路分区会一次处理整段重复值，全相等时一轮就能结束。代码选的是“中间位置上的元素”，并不保证这个值接近中位数，因而仍可能产生很不平衡的分区。
代码实现
class Solution {
public int findKthLargest(int[] nums, int k) {
int target = k - 1;
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int[] equalRange = partition(nums, left, right);
if (target < equalRange[0]) {
right = equalRange[0] - 1;
} else if (target > equalRange[1]) {
left = equalRange[1] + 1;
} else {
return nums[target];
}
}
return -1;
}
private int[] partition(int[] nums, int left, int right) {
int pivot = nums[left + (right - left) / 2];
int greater = left;
int idx = left;
int less = right;
while (idx <= less) {
if (nums[idx] > pivot) {
// greater 左侧都大于 pivot，等值区间会被留在中间。
swap(nums, greater, idx);
greater++;
idx++;
} else if (nums[idx] < pivot) {
swap(nums, idx, less);
less--;
} else {
idx++;
}
}
return new int[] {
greater,
less
};
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func findKthLargest(nums []int, k int) int {
target := k - 1
left := 0
right := len(nums) - 1
for left <= right {
equalLeft, equalRight := partition(nums, left, right)
if target < equalLeft {
right = equalLeft - 1
} else if target > equalRight {
left = equalRight + 1
} else {
return nums[target]
}
}
return -1
}
func partition(nums []int, left int, right int) (int, int) {
pivot := nums[left+(right-left)/2]
greater := left
idx := left
less := right
for idx <= less {
if nums[idx] > pivot {
// greater 左侧都大于 pivot，等值区间会被留在中间。
nums[greater], nums[idx] = nums[idx], nums[greater]
greater++
idx++
} else if nums[idx] < pivot {
nums[idx], nums[less] = nums[less], nums[idx]
less--
} else {
idx++
}
}
return greater, less
}
复杂度分析
- 时间复杂度：按随机排列输入进行平均分析为 $O(n)$，最坏为 $O(n^2)$。一轮分区与当前区间长度成正比；范围较均衡地缩小时，总扫描量呈几何级数；每轮只排除很少元素时则退化为平方级。当前代码固定选择中间位置，本身没有随机化期望保证。
- 空间复杂度：$O(1)$，原地交换并迭代收缩范围；Java 每轮返回的边界数组也只有固定两项。
关键点总结
[!green]
- 降序分区配合目标下标
k-1，分区方向和排名定义必须一致。- 四段状态明确区分已知大于、已知等于、未知和已知小于，指针更新来自这些含义。
- 与右端交换后不推进扫描指针，是为了检查换回来的未知元素。
- 三路分区消除了反复搜索等值元素的需要，但固定基准仍不保证所有输入下线性时间。
解法对比：
最小堆提供 $O(n\log(k+1))$ 的时间上界，使用 $O(k)$ 空间，不修改输入，也能逐个接收元素。
快速选择使用常数额外空间，但会打乱原数组。平均表现较好，当前确定性基准的最坏时间仍为 $O(n^2)$；这与只在目标一侧继续搜索并不矛盾。
易错点总结
[!yellow]
- 第
k大按出现次数计，不能把输入当成不同值的集合。- 最小堆保留最大的
k个，弹出的应是超额候选中最小的值。- 三路分区与右端交换后立即增加
idx，会跳过尚未分类的元素。- 固定取中间位置作为基准，不等于每轮都取得中位数，也不能据此承诺最坏线性时间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 703. 数据流中的第 K 大元素 | 简单 | 原题持续加入数据并查询第k大，本题只做一次选择，可用快速选择或堆。 |
| 347. 前 K 个高频元素 | 中等 | 同样挑选TopK，原题排名依据为元素频次，本题依据数值大小。 |