347. 前K个高频元素
描述
- Top K Frequent Elements
- 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例
- 给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。
注意
- 你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
思路
- 该题思路容易但编码难。很容易想出要统计每个元素出现的次数，然后取出其中前 k 高的。但采用何种数据结构就比较讲究了。
- 第一种思路是利用优先队列，即最大堆。这里注意存入堆中的元素是 pair 类型的，且以出现的次数为 key,值为 val.因为 pair 的排序是先比较 first，再比较 second。
- 第二种思路是利用桶排序，10个元素每个元素出现的次数是0 ~ 10，所以桶的个数为nums.size() + 1。注意可能有相同次数的元素出现，因此桶中存储的是一个数组而非单一元素。
(参考)
// 最大堆
class Solution_347_01 {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
priority_queue<pair<int, int>> pq;
vector<int> ret;
for (auto num : nums) {
mp[num]++;
}
for (auto val : mp) {
pq.push({val.second, val.first});
}
for (int i = 0; i < k; ++i) {
ret.push_back(pq.top().second);
pq.pop();
}
return ret;
}
};
// 桶排序
class Solution_347_02 {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
vector<vector<int>> bucket(nums.size() + 1);
vector<int> ret;
for (auto num : nums) {
mp[num]++;
}
for (auto val : mp) {
bucket[val.second].push_back(val.first);
}
for (int i = nums.size(); i >= 0; --i) {
for (int j = 0; j < bucket[i].size(); ++j) {
ret.push_back(bucket[i][j]);
if (!--k) return ret;
}
}
return ret;
}
};
