题目
给定一个非空数组，返回其中出现频率前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，将零碎时间利用起来】
