HHot 100C++ 图解

347. 前 K 个高频元素

一句话套路按频次桶排序(值域有界比堆更快)

题目描述

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入:nums = [1,1,1,2,2,3], k = 2

输出:[1,2]

示例 2:

输入:nums = [1], k = 1

输出:[1]

示例 3:

输入:nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出:[1,2]

 

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

 

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

思路

解法 A

频次 -> 小顶堆(容量 K),O(n log k)。

解法 B

桶排序,O(n):频次只可能落在 1..n,开 n+1 个桶,从高频桶倒序取 K 个。

—— 「值域有界」时,桶排序几乎总是比堆更快更好写。

输出顺序题目不要求,所以测试里先排序再比较。

图解

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

逐帧动画

1 / 3

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

C++17 题解

src/13_heap.cpp38 行
namespace lc0347 {
class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) ++cnt[x];
    // 小顶堆按频次淘汰:堆里始终保留频次最高的 k 个
    auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
      return a.second > b.second;  // 注意方向:> 让小顶堆
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap(cmp);
    for (auto& [num, c] : cnt) {
      heap.push({num, c});
      if ((int)heap.size() > k) heap.pop();
    }
    vector<int> ans;
    while (!heap.empty()) {
      ans.push_back(heap.top().first);
      heap.pop();
    }
    return ans;
  }

  vector<int> topKFrequentBucket(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) ++cnt[x];
    vector<vector<int>> bucket(nums.size() + 1);  // 下标 = 出现次数
    for (auto& [num, c] : cnt) bucket[c].push_back(num);
    vector<int> ans;
    for (int f = (int)bucket.size() - 1; f >= 0 && (int)ans.size() < k; --f)
      for (int num : bucket[f]) {
        ans.push_back(num);
        if ((int)ans.size() == k) break;
      }
    return ans;
  }
};
}

单元测试

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

TEST q347_top_k_frequent17 行
lc0347::Solution s;
auto sorted = [](vector<int> v) {
  sort(v.begin(), v.end());
  return v;
};
vector<int> a{1, 1, 1, 2, 2, 3};
CHECK_EQ(sorted(s.topKFrequent(a, 2)), sorted(vector<int>{1, 2}));
CHECK_EQ(sorted(s.topKFrequentBucket(a, 2)), sorted(vector<int>{1, 2}));
vector<int> b{1};
CHECK_EQ(s.topKFrequent(b, 1), vector<int>{1});
vector<int> c{-1, -1};
CHECK_EQ(s.topKFrequent(c, 1), vector<int>{-1});
vector<int> d{1, 2};  // 频次相同,任取一个;k=2 时都要
CHECK_EQ(sorted(s.topKFrequent(d, 2)), sorted(vector<int>{1, 2}));
CHECK_EQ(sorted(s.topKFrequentBucket(d, 2)), sorted(vector<int>{1, 2}));
vector<int> e{4, 4, 4, 3, 3, 2, 1, 1, 1, 1};
CHECK_EQ(sorted(s.topKFrequentBucket(e, 2)), sorted(vector<int>{1, 4}));

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