HHot 100C++ 图解

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, ...) —— 一行,工程里最该用这个。

图解

3 0 2 1 3 2 1 3 2 4 4 5 5 6 5 7 6 8
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/13_heap.cpp44 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q215_kth_largest_element16 行
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);

↑↓ 选择↵ 打开/ 随时唤起