在处理数组中查找第 K 大或第 K 小元素这类问题时，很多人第一反应是排序。虽然排序能解决问题，但时间复杂度通常是 O(NlogN)。如果数据量很大，我们其实不需要完全有序，只需要把目标元素'挖'出来即可。这时候，基于快速排序思想的**快速选择算法（Quick Select）**就派上用场了，它的平均时间复杂度可以逼近 O(N)。
45. 数组中的第 K 个最大元素
题目链接
215. 数组中的第 K 个最大元素 - 力扣（LeetCode）
题目描述
题目示例
解题思路
这道题的核心在于利用快排的分区思想。在标准的三路划分快排中，我们将数组分为 [left, l]、[l+1, r-1]、[r, right] 三个区间，分别对应小于基准、等于基准、大于基准的元素。
对于找第 K 大的数，我们不需要递归处理所有区间。只需计算每个区间的长度，判断目标值落在哪个区间内：
- 如果右边区域（大于基准的部分）元素个数 >= k，说明第 k 大就在右边，直接递归右半部分。
- 如果右边区域 < k，但中间加右边区域 >= k，说明第 k 大就是基准值本身。
- 否则，目标在左边区域，此时需要调整 k 的值继续向左搜索。
这种剪枝策略避免了不必要的递归，显著提升了效率。
代码实现
class Solution {
public:
int Top_k(vector<int>& nums, int left, int right, int k) {
if(left == right) {
return nums[left];
}
// 随机选择基准元素，避免最坏情况
int key = nums[() % (right - left + ) + left];
l = left - , r = right + , i = left;
(i < r) {
(nums[i] > key) {
(nums[i], nums[--r]);
} (nums[i] < key) {
(nums[i++], nums[++l]);
} {
i++;
}
}
(right - r + >= k) {
(nums, r, right, k);
}
(right - l >= k) {
key;
}
{
(nums, left, l, k - (right - l));
}
}
{
(());
(nums, , nums.() - , k);
}
};
