题目
给定一个非空数组,返回其中出现频率前K高的元素。
示例1:
输入:nums = [1,1,1,2,2,3], k = 2
输出:[1,2]
示例2:
输入:nums = [1], k = 1
输出:[1]
思路
- 首先,提到出现频率,就能想到,使用字典中key-value形式,当有重复关键字出现,value就加一。
- 其次,本题要求返回出现频率前K高的元素,即需要对value进行排序,依次输出前k个。这恰好符合堆的性质。难点在于,怎么按map中的value值排序!
- 本题使用hashmap统计数组中每个元素出现的个数,然后维护一个存储键值对且容量为k的优先队列,并自定义该优先队列的排序方式,实现最小堆,即最后优先队列里存储的是最大的三个值。而顶部是当前出现频率最小的元素,最后倒序出队访问即可。
解答
class Solution {
public:
typedef pair<int, int> mypair; //key-value
struct cmp { //自定义排序方法
bool operator()(const mypair &left, const mypair &right) const
{
return left.second > right.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> ans(k, 0);
unordered_map<int, int> hash;
priority_queue<mypair, vector<mypair>, cmp> que; //优先队列
for(auto key : nums) //统计每个元素的频率
hash[key]++;
for(auto iter : hash){ //维护容量为k的最小堆
que.push(iter);
if(que.size() > k)
que.pop();
}
while(k > 0){
ans[k-1] = que.top().first; //倒序输出
que.pop();
k--;
}
return ans;
}
};
【关注公众号DoCode,每日一道LeetCode,将零碎时间利用起来】