👋 欢迎阅读
🔥愿旖旎· 个人主页
📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》
🌄 钱塘江上潮信来，今日方知我是我
✨当前学习内容：《快速排序》
一.题目
215. 数组中的第K个最大元素 - 力扣（LeetCode）
🎯 欢迎来到「数组中的第K个最大元素」题解之旅！本文将带你从"在一堆数里找出第 K 大的那个"这一直观场景出发，深入理解快速选择（随机基准 + 三路划分）的巧妙运用，并掌握如何按分区大小定位 k 且只递归一侧来在平均 O(n) 内找到第 K 大元素。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 215 题，给定整数数组
nums和整数k，返回第 k 大的元素（按降序数第 k 个）。本质上，不必把整个数组排好序，只需确定 k 落在划分后的哪一段，问题转化为快速选择（Quick Select）。明确学习目标：掌握三路划分（大于 / 等于 / 小于）与随机基准防退化，理解
leftSize与midSize的定位逻辑，并熟练处理重复元素与右区 k 值换算等边界情况。准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
nums = [3,2,1,5,6,4]，k = 2输出5）。
本文将从问题转化、三路划分、k 值定位、随机化到代码实现，层层递进。即使你对快速选择还不熟悉，我们也会从"大的扔左边、小的扔右边，看 k 落在哪一堆"这一直觉出发，让你轻松抓住核心思想——分三堆，k 在哪堆就只钻哪堆。现在，让我们一起随机选基准、三路划分，找到第 K 大的元素吧！ 🎯🔍
二、算法分析
1. 问题分析（前置分析）
- 题目要求：返回
nums中第 k 大的元素（降序第 k 个，k从 1 开始计数）。 - 关键约束：
n可达10⁵；k合法（1 ≤ k ≤ n）；元素可含大量重复；要求比全排序更高效。 - 核心思路：全排序是"把所有元素排好"，找第 k 大只需知道它落在哪一段——快速选择每次划分后只递归 k 所在的那一侧，平均 O(n)。
📌 例子：为什么不必全排序
nums = [3,2,1,5,6,4]，k = 2（第 2 大是 5）：全排序需把 6 个数排成[6,5,4,3,2,1]，代价 O(n log n)；而快速选择一次划分就能确认"比 4 大的有 2 个"，k = 2正好落在左区，只钻这一侧，其余元素完全不用处理——"选择"省掉了"排序"中不需要的那部分工作。
2. 算法策略（随机基准 + 三路划分 + 单侧递归）
核心步骤：
- 随机选基准：
key = nums[rand() % 区间长度 + l]，入口srand(time(NULL))调用一次即可。 - 三路划分（降序）：
left = l-1、right = r+1、i = l；nums[i] > key换到左区、nums[i] == key跳过、nums[i] < key换到右区。 - 统计三区大小：左区（全
> key）长度leftSize = left - l + 1；中区（全== key）长度midSize = right - left - 1。 - 按 k 定位：
k <= leftSize→ 目标在左区，递归[l, left]，k 不变；k <= leftSize + midSize→ 目标在中区（全是 key），直接返回 key；- 否则 → 目标在右区，递归
[right, r]，k 减去leftSize + midSize。
- 返回：递归单侧收敛到答案。
📊 示例（nums = [3,2,1,5,6,4]，k = 2，基准key = 4）：
| 步骤 | i | nums[i] | 与 key=4 比较 | 操作 | left | right |
|---|---|---|---|---|---|---|
| 初始 | 0 | 3 | 3 < 4 | 换到右区（--right = 5） | -1 | 5 |
| ① | 0 | 4 | 4 == 4 | 跳过（i++） | -1 | 5 |
| ② | 1 | 2 | 2 < 4 | 换到右区（--right = 4） | -1 | 4 |
| ③ | 1 | 6 | 6 > 4 | 换到左区（++left = 0，i++） | 0 | 4 |
| ④ | 2 | 1 | 1 < 4 | 换到右区（--right = 3） | 0 | 3 |
| ⑤ | 2 | 5 | 5 > 4 | 换到左区（++left = 1，i++） | 1 | 3 |
| 结束 | 3 | — | i == right | 划分完成 | 1 | 3 |
划分后数组为[6,5,4,1,2,3]：左区[0,1] = [6,5]（leftSize = 2）、中区[2,2] = [4]（midSize = 1）、右区[3,5] = [1,2,3]。k = 2 ≤ leftSize = 2→ 递归左区[0,1]，最终得到第 2 大 =5✅。
3. 正确性说明（简单版本）
- 划分不变量：循环每轮保持
[l, left]全> key、[left+1, right-1]全== key、[right, r]全< key，三个分支各做一次合法转移，不破坏不变量。 - 定位正确：左区有
leftSize个元素都比key大，所以第 k 大若k ≤ leftSize必在左区；若k落在中区，说明第 k 大就是key本身（中区全是相等的 key），可直接返回；否则k' = k - leftSize - midSize才是它在右区内的排名。 - k 换算正确：右区元素都
< key，它们前面已有leftSize + midSize个更大的元素，故右区内找第k - leftSize - midSize大，换算不漏不错。 - 随机化保证期望性能：随机基准使划分期望对半，递归深度期望 O(log n)、总代价期望 O(n)；极小概率退化为 O(n²)。
📌 例子：为什么"中区可以直接返回 key"
nums = [3,3,2,1]，k = 2，取key = 3：划分后左区为空（leftSize = 0）、中区[3,3]（midSize = 2）、右区[2,1]。k = 2 ≤ 0 + 2，说明第 2 大正好是key = 3（降序为[3,3,2,1]，第 2 个就是 3）✅——中区可能包含多个相同值，k 落在这里时答案就是 key，无需继续递归，这也是三路划分能高效处理重复元素的原因。
4. 实现细节（边界防护）
- 初始化：
srand(time(NULL))在findKthLargest入口调用一次；qsort(nums, 0, n-1, k)，k为1 起始的排名。 - 边界防护：
left = l-1、right = r+1为虚拟边界（++left/--right首次落在l/r）；getRandom中rand() % (r-l+1) + l保证基准落在[l, r]；l == r时区间长度 1，取模后仍落在该位置，不会越界；k始终满足1 ≤ k ≤ 当前区间长度，故递归不会进入空区间。 - 复杂度：平均O(n)、最坏 O(n²)（随机化后概率极低）；空间为期望 O(log n)的递归栈（最坏 O(n)）。
- 关键操作：
int key = getRandom(nums, l, r);（随机基准）、swap(nums[++left], nums[i++])/swap(nums[--right], nums[i])（左右分区）、k - leftSize - midSize（右区排名换算）。
📌 例子：虚拟边界与单元素区间
nums = [1]、k = 1：l = r = 0，key = nums[0] = 1；left = -1、right = 1；nums[0] == key→i = 1，此时i < right（1 < 1）不成立，循环结束。leftSize = -1 - 0 + 1 = 0、midSize = 1 - (-1) - 1 = 1，k = 1 ≤ 0 + 1→ 返回key = 1✅。虚拟边界让"先自增/自减再使用"永远落在合法下标，单元素区间也无需特判。
5. 返回值（目标映射）
- 返回第 k 大的元素值：若落在中区直接返回
key，否则递归收敛后返回该值，对应题目"返回第 k 大的元素"。
三.代码
class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); srand(time(NULL)); // 随机种子只需设置一次 return qsort(nums, 0, n - 1, k); // k 从 1 开始计数 } // 快速选择：在 [l, r] 内找第 k 大 int qsort(vector<int>& nums, int l, int r, int k) { // 1. 随机选基准，避免有序输入退化为 O(n²) int key = getRandom(nums, l, r); // 2. 三路划分（降序）：大于 key 归左区、等于留中区、小于归右区 int i = l; int left = l - 1; // 左区右边界（虚拟位置） int right = r + 1; // 右区左边界（虚拟位置） while (i < right) { if (nums[i] > key) { swap(nums[++left], nums[i++]); // 大数归左，游标前进 } else if (nums[i] == key) { i++; // 相等留在中区 } else { swap(nums[--right], nums[i]); // 小数归右，游标不动（换入元素未检查） } } // 3. 划分结果：[l, left] 为左区、[left+1, right-1] 为中区、[right, r] 为右区 int leftSize = left - l + 1; // 比 key 大的元素个数 int midSize = right - left - 1; // 等于 key 的元素个数 // 4. 按 k 落在哪一区决定去留 if (k <= leftSize) { return qsort(nums, l, left, k); // 左区找第 k 大 } else if (k <= leftSize + midSize) { return key; // 落在中区：答案就是 key } else { return qsort(nums, right, r, k - leftSize - midSize); // 右区：换算新的排名 } } // 随机取 [l, r] 内的一个元素值作为基准 int getRandom(vector<int>& nums, int l, int r) { int q = rand(); return nums[q % (r - l + 1) + l]; } };四、易错点分析
难点1：三路划分的方向必须与"第 k 大"对应
if (nums[i] > key) { swap(nums[++left], nums[i++]); // 大于 key 放左边 } else { swap(nums[--right], nums[i]); // 小于 key 放右边 }本题要第 k 大，所以数组应按降序分区：> key的元素必须放左区（更大在前）。若沿用升序模板（< key放左），leftSize就变成"比 key 小的个数"，k <= leftSize的判定含义完全不同，定位会全部反掉（可能返回第 k 小而不是第 k 大）。方向与目标语义必须严格对齐，这是本题最容易犯的方向性错误。
难点2：< key分支中i不能前进
else { swap(nums[--right], nums[i]); // 注意：没有 i++ }--right处换到i位置的是尚未检查的元素，可能大于key、可能等于，因此必须原地重查；若写成swap(nums[--right], nums[i++])，这个换入元素会被直接跳过，若它大于 key 就会滞留在右区，分区错误。这与 75 题"2 分支不前进"是同一个道理——"右区换入未检查，必须停留"。
难点3：右区递归的k必须减去左区与中区
return qsort(nums, right, r, k - leftSize - midSize);右区元素全都< key，它们前面已有leftSize + midSize个更大的元素；因此在右区内要找的是"全局第 k 大在右区内的排名"，即k - (leftSize + midSize)。若漏减（直接传k），递归会重复计算前面那些更大的元素，导致定位偏移、答案错误。三个分支中，只有右区需要换算 k。
难点4：leftSize/midSize的公式与区间衔接
int leftSize = left - l + 1; int midSize = right - left - 1;left是左区最右元素的下标（左区为[l, left]），故leftSize = left - l + 1；中区为[left+1, right-1]，故midSize = (right-1) - (left+1) + 1 = right - left - 1。若把midSize误写成right - left，就会把right处的元素也算进中区（它实际属于右区），导致k的定位差一，答案偏移。
难点5：随机基准——srand只调一次，且返回的是"值"
int getRandom(vector<int>& nums, int l, int r) { int q = rand(); return nums[q % (r - l + 1) + l]; // 返回元素“值”，不是下标 }getRandom返回的是基准值key（用于比较），而不是基准的下标——后续划分与key比较、中区直接return key，都依赖它是值。若误改成返回下标，if (nums[i] > key)就变成"拿值比下标"，逻辑全错。另外srand(time(NULL))应在入口调用一次（每次递归都调会用同一秒的种子，失去随机性）；q % (r-l+1) + l映射到[l, r]，l == r时区间长 1 仍安全，但rand() % range存在极轻微取模偏差，对本题无实际影响。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「数组中的第K个最大元素」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀 动手实践在 LeetCode 上提交代码，尝试不同的测试用例。
💡 深入思考
- 本题采用三路划分 + 单侧递归。请问为什么定位到 k 所在分区后只需递归一侧？与全排序的本质区别是什么？
- 中区（全等于 key）可以直接返回 key。请问为什么不用继续递归？用
nums = [3,3,2,1]、k = 2说明。 - 右区递归传的是
k - leftSize - midSize。请问为什么必须减去这两个数量？漏减会得到什么？
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路
📌 深入思考答案
- 划分后三区大小已知：左区有
leftSize个更大的、中区有midSize个相等的。k落在哪一区就能确定答案所在区间，其余两区不可能包含第 k 大，故只需递归一侧；全排序则要把两侧都排好，代价 O(n log n)，而这里期望 O(n)。 - 中区内所有元素都等于 key，它们的"大排名"连续且都等于同一个值——若
k落在中区，说明第 k 大就是 key 本身，[3,3,2,1]中k=2时答案正是 3，无需再细分；这也让重复元素不会导致退化。 - 右区元素都小于 key，全局排名要跳过"左区 + 中区"共
leftSize + midSize个更靠前的元素；故右区内应找第k - leftSize - midSize大。漏减会把前面那些更大的元素重复计入，定位偏移。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨
)
