【LC 215】数组中的第 K 个最大元素：快速选择只在回答「我排第几」
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。要求设计时间复杂度为 O(n) 的算法。
示例：[3,2,1,5,6,4], k=2 → 5。
腾讯、阿里、蚂蚁 TopK 方向的必考题。它有一个 O(n log n) 的平凡解（排序），而题目要 O(n) —— 这个"再快一档"的全部秘密，藏在对
分区的一个重新解读里。
一、先把"第 k 大"翻译对
1.1 第 k 大是"第 k 个位置"，不是"第 k 个不同的值"
官方第二个例子专门用来钉死语义：
nums = [3,2,3,1,2,4,5,5,6], k = 4，输出 4。
把它降序排好：
[6, 5, 5, 4, 3, 3, 2, 2, 1]。第 4 个位置上是
4。
注意这里有两个
5 —— 它们
各占各的位置。如果你理解成"第 4 个
不同的值"，会算出 3（不同值降序是
[6,5,4,3,2,1]，第 4 个是 3）。
题目要的是前者：重复元素在排名里各算一个席位。
所以更准确的题面应该是：
"把它排好序之后，下标在第 k 位上的那个数"。这句话直接给出了第一种解法：
def findKthLargest(nums, k):
nums.sort()
return nums[len(nums) - k]
一行，O(n log n)，能过，但面试官下一句一定是："题目要求 O(n)，怎么办？" —— 别急，先看清这行代码里那个最容易写错的
下标。
1.2 索引换算：第 k 大 = 升序第 n-k 位
升序数组里，第 k 大是
倒数第 k 个，也就是下标
n - k（0 基）：
nums = [3, 2, 1, 5, 6, 4], n = 6, k = 2
升序：[1, 2, 3, 4, 5, 6]
↑
下标 n-k = 4，值 5 ✓
写成
k - 1 是最常见的错误 —— 那找的是
第 k 小。这个 off-by-one 之所以高频，是因为"第 k 大"和"第 k 小"在代码里只差一个字符，而样例往往测不出来：
[3,2,1,5,6,4] 配
k=2，如果数组恰好对称（比如
[1,2,3,2,1]），两种理解会给出同一个答案。
这个系列反复出现一个模式：官方样例恰好掩盖 bug。 这里的版本是——用对称数组的样例，验证不了你有没有把"大"写反。
二、解法梯队总览
题目要的 O(n) 对应第三行。先讲它，再讲什么时候堆反而更好。
三、快速选择：分区之后，位置即排名
3.1 核心观察
快速排序做一次分区（partition）之后，有一件事是
确定的：
枢轴（pivot）落在它最终排序位置上。因为它左边的元素全部
<= 它，右边的全部
> 它 —— 无论数组最后怎么排，这个元素就在这一位。
而"落在最终排序位置上"有一个更重要的解读：
这个位置就是它的排名。
于是"找第 k 大"变成一个判断题：
- 枢轴位置 == 目标位 → 它就是答案，结束；
- 枢轴位置 < 目标位 → 答案在右边，左边（含枢轴）全部淘汰；
- 枢轴位置 > 目标位 → 答案在左边，右边（含枢轴）全部淘汰。
快排要递归两边，快速选择只进一边 —— 这就是从 O(n log n) 降到 O(n) 的全部原因。
3.2 逐帧推演
用官方例 1：
[3, 2, 1, 5, 6, 4]，
k = 2。
n = 6，目标位
n - k = 4（升序下标）。分区用 Lomuto 方案：枢轴取区间最右端，
i 指向"小于等于区"的下一个空位，
j 从左往右扫。
14 帧的完整推演表（与状态机
quickSelectSteps.js 的实际输出逐行核对过）：
两个值得盯住的瞬间：
- 第 8 帧：枢轴 4 落在下标 3，但目标位是 4。
3 < 4，说明答案在右边 —— 左边 4 个元素（含枢轴）从此一眼都不看。快速选择的"省"，全部省在这一步。
- 第 12 帧：枢轴 5 落在下标 4，正好是目标位。左边 4 个都不比它大、右边 1 个都比它大 —— 排名确凿，不用再比任何东西。
3.3 为什么敢只进一边（正确性）
"左边那 4 个以后再也不看"听起来太自信了。论证其实只有两句：
- 分区之后，枢轴位置的排名已经确定：它就是升序数组的第
pivotIdx 位（0 基）。如果 pivotIdx == target，答案就是它，其他任何元素都不可能在这个位置上。
- 如果
pivotIdx < target，目标位在枢轴右边 —— 而右边那些元素的相对顺序虽然还乱着，但它们就是升序数组下标 pivotIdx+1..n-1 上的全部候选。目标位 target > pivotIdx 落在这段里，左边那些元素排名全都 <= pivotIdx < target，不可能出现在目标位上。
所以淘汰不是"大概率的剪枝"，是
确定性的排除。这个性质和 LC 3 滑动窗口里"left 只会右移"是同一类不变量：
每一步淘汰都不可逆，且不漏。
3.4 迭代写法
收敛逻辑是"区间收缩"，用迭代写最自然，还省掉递归栈：
import random
def findKthLargest(nums, k):
target = len(nums) - k # 第 k 大 = 升序下标 n-k
left, right = 0, len(nums) - 1
while True:
pivot = nums[right] # 生产代码应该随机化，见第五节
i = left
for j in range(left, right):
if nums[j] <= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
if i == target:
return nums[i]
elif i < target:
left = i + 1 # 答案在右边
else:
right = i - 1 # 答案在左边
四、复杂度：O(n) 是怎么来的
4.1 平均情形的几何级数
设每次分区能砍掉一半候选（期望意义下），总扫描量是：
n + n/2 + n/4 + ... = 2n ≈ O(n)
随机枢轴下，期望比较次数是
2n + o(n) 量级 —— 常数 2 的来源正是这个级数。
分区本身每轮 O(区间长度)，级数求和收敛在 2n。
4.2 最坏情形：不是理论装饰，是真实会踩的坑
两种输入会让"每轮砍一半"退化成"每轮只砍一个"：
情形一：有序数组 + 固定取末尾当枢轴。 升序数组
[1,2,...,n] 找最小值（k=n）时，枢轴恰好是区间最大值，每轮只能砍掉自己 —— n 轮、每轮扫一遍，
O(n²)。我的状态机实测：
n = 6，升序 + pivot 取末尾 + 找最小：5 轮分区（随机枢轴只要 2 轮）
n = 8，同上：7 轮分区（随机枢轴 2 轮）
这个更反直觉 —— 就算你把比较写成
<=，全相同元素的数组依然是 Lomuto 的最坏情况：每个元素都
<= 枢轴，
i 一路走到末尾，枢轴归位后落在原地，每轮还是只砍掉 1 个。实测
[5,5,5,5,5,5] 找最小值要 5 轮。
两个修复：
- 随机化枢轴：随机挑一个位置换到末尾再分区。最坏情况在理论上仍存在（运气差到底），但任何固定输入能触发它的概率随 n 超指数衰减，工程上视作不会发生；
- 三路分区（荷兰国旗）：把数组分成"小于 / 等于 / 大于"三段，枢轴这一段一次性全部归位。全相同元素时等于区间直接清空 —— 这也是 Java 里对重复元素多的输入的标准优化。
LeetCode 官方题解用的就是"随机化 + 三路划分"。工程库里的做法更进一步：C++ 的
std::nth_element 用
introselect —— 随机枢轴为主，递归深度超过 2·log n 就切换到 BFPRT（中位数的中位数），把最坏情况彻底钉死在 O(n)。面试时能主动说出"固定枢轴在最坏情况会退化，所以要随机化，全相同元素要三路"，比背出 O(n) 本身值钱。
4.3 四种解法放一起
五、堆解法：O(n log k) 什么时候比 O(n) 更好
5.1 算法
维护一个
容量为 k 的小根堆，遍历数组：堆没满就压入；满了且当前元素比堆顶大，就弹出堆顶再压入。扫完后
堆顶就是第 k 大 —— 堆里始终装着"到目前为止最大的 k 个"，堆顶是其中最小的一个。
import heapq
def findKthLargest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
5.2 一个常见误区：为什么是小根堆不是大根堆
直觉上"找最大的 k 个"该用大根堆，但那样必须把全部 n 个元素装进堆再弹 k 次，时间 O(n + k log n)、空间 O(n)。
小根堆装的是"k 个候选中最小的那个"，它始终守在"第 k 大"这个门槛上：新元素想进前 k，先得打赢门槛。
（LC 3 那篇说过"判据在 cur 身上不在 x 身上"，这里是同款思想：
门槛本身才是主角，新元素只是挑战者。）
5.3 快速选择 vs 堆：四维对照
面试追问"这两个怎么选"时，比"谁快"更重要的是这四行：
两个"能/改"经常被忽略，却是工程选型的关键：数据是流式到达的，快速选择直接出局；调用方不允许你动它的数组，同理。
堆慢在渐近意义上从未发生 —— O(n log k) 在 k 接近 n 时确实退化成 O(n log n)，但换来的是稳定性和流式能力。 反过来，面试白板上一道"写出来"的题，堆十行内写完且没有最坏情况，快速选择写错分区边界就死循环 —— 所以很多面试官建议：
先写堆，再主动提快速选择作为优化。
六、海量数据 TopK：10 亿个数找前 100 大
把上面的选择推到工程尺度 —— 前提变了：
单机内存装不下全部数据。10 亿个整数约 4 GB（裸存），加上结构开销远超单机可用内存；如果是日志行，更是几十上百 GB。
6.1 前提一：单机能存下"k 个"就够了 —— 小根堆
10 亿找前 100 大，只需要维护一个
100 容量的小根堆：
- 内存：100 个元素，忽略不计；
- 扫描：一遍。文件顺序读（哪怕从磁盘、从多台机器汇聚），边读边喂给堆；
- 时间：O(n log k) = 10⁹ × log₂100 ≈ 10⁹ × 7，几十秒级。
这就是 5.3 节"堆能流式"的直接变现：快速选择在这里完全出局 —— 它需要把数组整个握在手里做随机访问，而海量数据给不了。
6.2 前提二：数据分散在多台机器 —— 分桶归并
如果数据本来就散在多台机器 / 多个文件上，先
各自取本地 Top 100（各自用堆），再把 100 份局部 Top100 归并成全局 Top100 —— 100 × 100 = 一万条，随便放。
每个局部候选都"打赢过本地的 99 个对手"，全局前 100 一定藏在它们之中 —— 这是归并正确性的根据。
（如果问题换成"出现次数最多的前 K 个
词"，还会多一层麻烦：去重后的词表本身装不进内存，要先哈希分桶 —— 那是 LC 347 的海量版，下一篇讲。）
6.3 选型小结
七、Java 版
class Solution {
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k; // 第 k 大 = 升序下标 n-k
int left = 0, right = nums.length - 1;
while (true) {
int idx = partition(nums, left, right);
if (idx == target) return nums[idx];
else if (idx < target) left = idx + 1;
else right = idx - 1;
}
}
private int partition(int[] a, int left, int right) {
int r = left + (int) (Math.random() * (right - left + 1)); // 随机化
swap(a, r, right);
int pivot = a[right], i = left;
for (int j = left; j < right; j++) {
if (a[j] <= pivot) {
swap(a, i, j);
i++;
}
}
swap(a, i, right);
return i;
}
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
}
堆版用
PriorityQueue（默认就是小根堆，不用翻极性）：
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
}
八、边界情况与常见坑
坑一：k - 1 与 n - k。 前文已讲，第三种确认方式：
k = n 时答案应该是数组最小值 —— 用这个特例在脑子里过一遍你的下标公式。
坑二：固定枢轴在有序输入上超时（TLE）。 LeetCode 215 的测试数据里有精心构造的有序大数组，固定取末尾的 Lomuto 提交会直接超时。随机化一行就能修。
坑三：<= 还是 <。 Lomuto 分区写
< 的话，等于枢轴的元素会被甩到右边，全相同元素退化得更狠；标准写法是
<=，配合三路分区处理大规模重复。
坑四：快排口径记混。 快速选择平均 O(n) 的前提是
只递归一边。如果你发现自己在两边都递归了，那写的是快排不是快速选择 —— O(n log n)，题目的 O(n) 要求就没满足。
坑五：堆方法里忘了维护容量。 只 push 不 pop 的话堆会涨到 n 个，O(n log n)；容量超 k 必须立刻弹出堆顶。
九、变体
一图流的选择：
静态全量 + 想最快 → 快速选择；流式 / 只要前 k → 小根堆；键是小整数范围 → 桶排序。
十、面试怎么答
- 先给能跑的：排序一行，或堆十行。主动说复杂度；
- 再给题目要的：快速选择 O(n)，主动补一句"随机化枢轴避免有序输入退化，重复多可以三路分区"；
- 被追问海量数据：内存装得下 → 堆流式扫一遍；数据分散多机 → 局部 TopK + 归并；
- 自测两句话：
findKthLargest([3,2,1,5,6,4], 2) == 5，以及 findKthLargest([3,2,3,1,2,4,5,5,6], 4) == 4（第二个能钉死"位置不是不同值"）；
- 一句话总结：快速选择只在回答一个问题 —— 我排第几。分区之后位置即排名，答案自己浮出来。
系列下一篇：【LC 347】前 K 个高频元素 —— 同一个 TopK 骨架，键换成频率之后出现了结构性的免费午餐。本文动画 14 帧，与状态机单测（36 例，与排序/小根堆两个独立参考解三向交叉验证）逐行核对过。