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] <= 104k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一,换句话说,数组中前
k个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
思路
解法 A
频次 -> 小顶堆(容量 K),O(n log k)。
解法 B
桶排序,O(n):频次只可能落在 1..n,开 n+1 个桶,从高频桶倒序取 K 个。
—— 「值域有界」时,桶排序几乎总是比堆更快更好写。
输出顺序题目不要求,所以测试里先排序再比较。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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}));