45. 数组中的第 k 个最大元素
题目描述
给定整数数组 nums 和整数 k，请返回该数组中第 k 个最大的元素。
注意这里需要的是排序后第 k 大的元素，而不是第 k 个不同的元素。例如输入 [3,2,1,5,6,4]，k=2，输出应为 5。
解法思路：快速选择算法
这道题最直观的做法是排序，时间复杂度为 O(NlogN)。但如果数据量很大，我们其实不需要完全有序，只需要找到第 k 个位置即可。这时候**快速选择算法（Quick Select）**就派上用场了。
它的核心思想来源于快速排序的分区操作（Partition）。在快排中，我们将数组划分为小于基准、等于基准、大于基准三部分。利用这个特性，我们可以判断目标元素究竟落在哪个区间：
- 计算区间长度：统计当前分区后，右侧区域（大于基准）和中间区域（等于基准）的元素个数。
- 定位目标：
- 如果右侧区域元素个数 >= k，说明第 k 大就在右边，递归处理右半部分。
- 如果右侧 + 中间区域个数 >= k，说明基准值就是我们要找的第 k 大元素。
- 否则，目标在左侧，需要在左边继续查找，同时更新 k 的值（减去已排除的元素数量）。
这种三路划分（Dutch National Flag 问题变种）能有效处理大量重复元素的情况，避免退化。
C++ 参考实现
class Solution {
public:
// 快速选择主函数，寻找第 k 大的数
int Top_k(vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
int l = left - 1, r = right + 1, i = left;
// 随机选择基准元素，防止最坏情况
int key = nums[rand() % (right - left + 1) + left];
// 三路划分：[left, l] < key, [l+1, r-1] == key, [r, right] > 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 表示库存商品，以及整数 cnt 表示需要选取的商品数量。返回数组中最小的 cnt 个数。
例如输入 [3,2,3,1,2,4,5,5,6]，cnt=4，输出 [1,2,3,3]。
解法思路
这道题与上一题非常相似，只是方向相反。我们需要找最小的 k 个数，本质上还是利用快速选择的分区思想。
相比堆排序（O(NlogK)）或全排序（O(NlogN)），快速选择算法的平均时间复杂度可以逼近 O(N)。虽然代码逻辑稍显巧妙，但在处理大规模数据时性能优势明显。
对比其他方案
- 全排序：简单直接，但效率较低。
- 堆排序：适合流式数据，空间占用小，但常数因子较大。
- 快速选择：原地修改数组，平均速度最快，适合一次性查询场景。
C++ 参考实现
class Solution {
public:
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
if (cnt == 0) {
return {};
}
srand(time(NULL));
// 调用快速选择，将数组前 cnt 个元素调整为最小的 cnt 个
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++;
}
}
// 根据分区结果决定下一步搜索区间
if (l - left + 1 >= cnt) {
return Top_k(nums, left, l, cnt);
} else if (r - left >= cnt) {
return;
} else {
return Top_k(nums, r, right, cnt - (r - left));
}
}
};
总结
这两道题的核心都在于分治策略。通过随机化基准值和三路划分，我们避免了传统快排在重复元素较多时的性能退化。在实际工程中，如果面对海量数据且只需部分有序信息，优先尝试快速选择算法，往往能获得比排序更好的性能表现。
