LeetCode 215中等快速选择 · Top K
数组中第 K 个最大元素 图解题解
这道题到底在问什么
给一个数组，找出其中第 k 个最大的元素（是排序后的第 k 大，不是第 k 个不同的）。
- nums
- [3, 2, 1, 5, 6, 4]
- k
- 2
- 输出
- 5
最优解：一步一步想明白
- 3排一遍当然行，O(n log n)。但题目只要「第 K 大」一个数，把整个数组都排好太亏了——大量功夫花在了和答案无关的元素上。
- 4快排里 partition 一轮，能让基准归到它在排序结果里的下标 p。我们只关心「第 K 大该在的下标 target＝n−k」：若 p＝target，基准就是答案；若 p 偏小，目标在右半；偏大则在左半——只递归含目标的那一半，另一半直接扔。这就是快速选择比快排省的地方。
- 5target = n−k = 4六根柱子。第 2 大＝排序后下标 4 的那个数。我们不排序，用 partition 一步步把它逼出来。
- 6pivot = 4 · i = −1选最后一个数 4 当基准（橙色）。和快排一样，把比 4 小的甩到左边、不小于 4 的留右边。
- 7小区 = [3,2,1]从左扫：3、2、1 依次都小于 4，全部留在左区（它们本就在前面，原地不动）。接着 5、6 不小于 4，跳过。
- 8p = 3 · 左小右大把基准 4 换到小区后面：4 归位到下标 3（绿色）。左边 [3,2,1] 全小于 4、右边 [6,5] 全大于 4。partition 返回 p＝3。
- 9左半整段丢掉基准落在下标 3，比目标下标 4 小——这正是「位置不对」的分支：目标在它右边，所以只递归右半 [6,5]，左边那一整段（灰）看都不用看。
- 10pivot = 5 · 范围 [4,5]只在右半 [6,5] 里继续，选末尾 5 当基准。扫描：6 不小于 5，跳过。
- 11p = 4 · 6 留在右边6 大于 5，5 换到下标 4 归位，6 落到下标 5。partition 返回 p＝4。
- 12命中！基准 5 正好落在下标 4（＝ n−k），它就是第 2 大。返回 5，结束——全程没把整个数组排完，只动了含目标的那一侧。
- 15快排两边都递归（要全排好）；快速选择只要找第 K 个，只走含目标的那一边，所以更快。「第 K 大/小」「找中位数」「Top-K」都用这套。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：第 K 大用下标 k
✓ 对：下标是 n − k
第 K 大＝排序后倒数第 k 个，下标要从右数；比如 [1..6] 求第 2 大，下标是 6−2＝4（值 5），写成 k＝2 会取到 3，结果整个错位
✗ 错：partition 后两边都递归
✓ 对：只递归含目标的一边
两边都递归就退化成快排 O(n log n)，丢了快速选择平均 O(n) 的优势
✗ 错：以为固定末尾基准就永远 O(n)
✓ 对：知道它最坏会退化、必要时随机化基准
本文代码为聚焦主逻辑用了固定末尾(nums[r]);但碰上已排好的数组每趟划分极不均→退化 O(n²),生产中应随机选基准再换到末尾
完整代码（Python / C++ / Java）
Python
class Solution:
def findKthLargest(self, nums, k):
target = len(nums) - k # 第 K 大 = 升序下标 n-k
l, r = 0, len(nums) - 1
while True:
pivot, p = nums[r], l # 选末尾当基准
for i in range(l, r):
if nums[i] < pivot: # 比基准小 → 换到左区
nums[i], nums[p] = nums[p], nums[i]; p += 1
nums[p], nums[r] = nums[r], nums[p] # 基准归位到 p
if p == target: return nums[p]
if p < target: l = p + 1 # 只看右半
else: r = p - 1 # 只看左半C++
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int target = nums.size() - k;
int l = 0, r = nums.size() - 1;
while (true) {
int pivot = nums[r], p = l;
for (int i = l; i < r; i++)
if (nums[i] < pivot) swap(nums[i], nums[p++]);
swap(nums[p], nums[r]); // 基准归位
if (p == target) return nums[p];
else if (p < target) l = p + 1; // 只看右半
else r = p - 1;
}
}
};Java
class Solution {
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k;
int l = 0, r = nums.length - 1;
while (true) {
int pivot = nums[r], p = l;
for (int i = l; i < r; i++)
if (nums[i] < pivot) { int t=nums[i]; nums[i]=nums[p]; nums[p]=t; p++; }
int t=nums[p]; nums[p]=nums[r]; nums[r]=t; // 基准归位
if (p == target) return nums[p];
else if (p < target) l = p + 1; // 只看右半
else r = p - 1;
}
}
}套路模板 · 快速选择（背下来）
# 快速选择骨架(平均 O(n))
target = n - k # 第 K 大 = 升序下标
while True:
p = partition(l, r) # 基准归位到 p
if p == target: return nums[p]
elif p < target: l = p + 1 # 只递归目标所在的一半
else: r = p - 1复杂度
时间复杂度
平均 O(n)
只递归一边，规模 n+n/2+n/4+… 约等于 2n；最坏 O(n²)（基准选偏，随机化避免）
空间复杂度
O(1)
原地分区，迭代写法无递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中第 K 个最大元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
堆和快速选择怎么选？+
堆 O(n log K)、稳定；快速选择平均 O(n) 更快但最坏 O(n²)(随机化可避免)。面试报快速选择更亮眼。
大小 K 的堆用大根还是小根？+
小根堆：留最大的 K 个，堆顶就是第 K 大。
快速选择最坏怎么办？+
随机选 pivot 或三数取中，避免划分极不均的最坏情况。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。