347. 前 K 个高频元素
3 min
题目
解法：桶排序
思路
使用哈希表统计频率，然后采用桶排序思想，将频率作为索引存储元素。
该方法正确是因为频率范围在 0 到 n 之间，创建 n+1 个桶可确保每个元素放入对应频率的桶中。从高频率桶向低频率桶遍历，能保证优先获取高频元素，且题目保证答案唯一性，因此按频率降序取 k 个元素即可得到正确答案。
- Step 1: 使用 unordered_map 统计每个数字出现的频率
- Step 2: 创建大小为 n+1 的桶数组，将数字放入对应频率的桶中
- Step 3: 从最高频率桶开始向下遍历，收集元素直到得到 k 个
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int x : nums) {
freq[x]++;
}
int n = nums.size();
vector<vector<int>> bucket(n + 1);
for (auto& [num, cnt] : freq) {
bucket[cnt].push_back(num);
}
vector<int> ans;
for (int i = n; i >= 1 && ans.size() < k; i--) {
for (int num : bucket[i]) {
ans.push_back(num);
if (ans.size() == k) break;
}
}
return ans;
}
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int x : nums) {
freq[x]++;
}
int n = nums.size();
vector<vector<int>> bucket(n + 1);
for (auto& [num, cnt] : freq) {
bucket[cnt].push_back(num);
}
vector<int> ans;
for (int i = n; i >= 1 && ans.size() < k; i--) {
for (int num : bucket[i]) {
ans.push_back(num);
if (ans.size() == k) break;
}
}
return ans;
}
};