215. 数组中的第 K 个最大元素
一句话套路K 个小顶堆 / 随机化快速选择
题目描述
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
思路
复杂度:sort 是 O(n log n),本题 n 可到 10^5,三种都比它快或相当。
解法 A
大小为 K 的小顶堆,O(n log k) / O(k) —— 数据流场景的唯一选择。
解法 B
快速选择(quickselect),平均 O(n) / O(1):随机选 pivot,做升序 Lomuto 划分(左边都 <= pivot,右边都 > pivot),第 K 大就是下标 target = n - k;只看包含 target 的那一半,递归。
随机化是必须的
否则有序输入会让它退化到 O(n^2)。
解法 C
nth_element(nums.end()-k, ...) —— 一行,工程里最该用这个。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0215 {
class Solution {
public:
// 解法 A:K 个小顶堆
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap; // 小顶堆
for (int x : nums) {
heap.push(x);
if ((int)heap.size() > k) heap.pop(); // 堆顶(最小)被淘汰
}
return heap.top(); // 留在堆里的是最大的 k 个,堆顶即第 k 大
}
// 解法 B:快速选择(原地,平均线性)
int findKthLargestQuickSelect(vector<int>& nums, int k) {
int target = (int)nums.size() - k; // 转成「升序第 target 个」
int lo = 0, hi = (int)nums.size() - 1;
mt19937 rng(1234567); // 固定种子让测试结果可复现
while (lo < hi) {
int p = partition(nums, lo, hi, rng);
if (p == target)
return nums[p];
else if (p < target)
lo = p + 1;
else
hi = p - 1;
}
return nums[lo];
}
private:
// Lomuto 划分 + 随机 pivot:返回 pivot 最终下标,左边都 <= nums[p]
static int partition(vector<int>& a, int lo, int hi, mt19937& rng) {
uniform_int_distribution<int> dist(lo, hi);
int r = dist(rng);
swap(a[r], a[hi]);
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; ++j)
if (a[j] <= pivot) swap(a[i++], a[j]);
swap(a[i], a[hi]);
return i;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0215::Solution s;
vector<int> a{3, 2, 1, 5, 6, 4};
CHECK_EQ(s.findKthLargest(a, 2), 5);
vector<int> b{3, 2, 3, 1, 2, 4, 5, 5, 6};
CHECK_EQ(s.findKthLargest(b, 4), 4);
vector<int> c{1};
CHECK_EQ(s.findKthLargest(c, 1), 1);
vector<int> d{7, 6, 5, 4, 3, 2, 1}; // 已排序(随机化 pivot 才不退化)
CHECK_EQ(s.findKthLargest(d, 3), 5);
// 快速选择:注意它会打乱原数组,所以传副本
vector<int> e{3, 2, 3, 1, 2, 4, 5, 5, 6};
CHECK_EQ(s.findKthLargestQuickSelect(e, 4), 4);
vector<int> f{3, 2, 1, 5, 6, 4};
CHECK_EQ(s.findKthLargestQuickSelect(f, 2), 5);
vector<int> g{2, 1};
CHECK_EQ(s.findKthLargestQuickSelect(g, 1), 2);