算法实战：数组中第 K 个最大元素与最小的 K 个数
45. 数组中的第 K 个最大元素
题目链接
题目描述
给定整数数组 nums 和整数 k，请返回该数组中第 k 个最大的元素。
题目示例
解法：快速选择算法
核心思路
快速选择（Quick Select）是快速排序的变种。在快排中，我们将数组划分为三个区域：小于基准、等于基准、大于基准。通过计算每个区域的元素数量，我们可以直接判断目标值落在哪个区间，从而避免对无关部分进行递归排序。
对于寻找第 k 大的元素，我们关注的是右侧的大数区域。如果右侧区域元素数量大于等于 k，说明目标就在右边；否则，我们需要调整 k 的值继续在左侧或中间查找。
C++ 代码实现
class Solution {
public:
int Top_k(vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
// 随机选择基准元素，避免最坏情况
int key = nums[rand() % (right - left + 1) + left];
int l = left - 1, r = right + 1, i = left;
// 三路划分：大于 key 的放右边，小于 key 的放左边
while (i < r) {
if (nums[i] > key) {
swap(nums[i], nums[--r]);
} else if (nums[i] < key) {
swap(nums[i++], nums[++l]);
} else {
i++;
}
}
// 若右边区域元素个数 >= k，说明第 k 大的数在右边区域
if (right - r + 1 >= k) {
return Top_k(nums, r, right, k);
}
// 若右边区域个数 < k，但中间加右边区域个数 >= k，说明第 k 大的数在中间区域
else if (right - l >= k) {
return key;
}
// 若中间加右边区域个数 < k，说明第 k 大的数在左边区域
else {
return Top_k(nums, left, l, k - (right - l));
}
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return Top_k(nums, 0, nums.size() - 1, k);
}
};
流程解析
46. 最小的 K 个数
题目链接
题目描述
仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示对应商品编号。请返回所有编号小于等于 cnt 的商品编号。
题目示例
解法：快速选择算法
核心思路
这道题与上一题逻辑相似，只是方向相反。我们要找最小的 k 个数，因此需要关注左侧的小数区域。同样采用三路划分策略，将小于基准的元素移到左侧，统计左侧区域数量即可定位目标区间。
相比全排序（O(NlogN)）和堆排序（O(NlogK)），快速选择在平均情况下时间复杂度接近 O(N)，效率更高。
C++ 代码实现
class Solution {
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
if (cnt == 0) {
return {};
}
srand(time(NULL));
Top_k(stock, 0, stock.size() - 1, cnt);
return vector<int>(stock.begin(), stock.begin() + cnt);
}
void Top_k(vector<int>& nums, int left, int right, int cnt) {
if (left == right) {
return;
}
int key = nums[rand() % (right - left + 1) + left];
int l = left - 1, r = right + 1, i = left;
while (i < r) {
if (nums[i] > key) {
swap(nums[i], nums[--r]);
} else if (nums[i] < key) {
swap(nums[i++], nums[++l]);
} else {
i++;
}
}
// 左侧区域（小于 key）元素个数 >= cnt，说明目标在左侧
if (l - left + 1 >= cnt) {
return Top_k(nums, left, l, cnt);
}
// 左侧加中间区域 >= cnt，说明目标已包含在左侧及中间，无需再分
else if (r - left >= cnt) {
return;
}
// 否则目标在右侧，需调整 cnt
else {
return Top_k(nums, r, right, cnt - (r - left));
}
}
};
流程解析
