1.题目
2.思路
（1）方法和【LeetCode215】数组中的第k个最大元素（小顶堆—priority_queue）相同（利用小顶堆，不断加入且保持优先队列恰好为k个元素）。不过注意是将每个元素出现次数加入小顶堆中——所以一开始用unordered_map统计每个元素的出现次数，而因为哈希表的key（即元素）也需要保存，所以优先队列priority_queue里的元素不是int型了：可以用pair<int,int>。
（2）在优先队列的排序参数需要重写（因为若直接用greater则是先对pair的first排序，再对second排序），而现在我们只要对second排序，所以符号重载：
struct cmp{ bool operator()(pair<int,int>&a,pair<int,int>&b){ return a.second>b.second; } };
（3）小顶堆的堆顶是最小的，所以为了根据频数找出前K大高频元素（从大到小），要依次将堆顶元素从末尾开始赋值给ans数组。
3.代码
class Solution { struct cmp{ bool operator()(pair<int,int>&a,pair<int,int>&b){ return a.second>b.second; } }; public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int>mp(nums.size());//key为i时出现的次数 for(int i=0;i<nums.size();i++){ mp[nums[i]]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>minheap; for(auto it=mp.begin();it!=mp.end();it++){ minheap.push(make_pair(it->first,it->second)); if(minheap.size()==k+1){ minheap.pop();//保持k个 } } vector<int>ans(k); for(int i=k-1;i>=0;i--){ ans[i]=minheap.top().first; minheap.pop(); } return ans; } };
4.不使用符号重载的版本
如果不使用符号重载，
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int i : nums) map[i] ++; //遍历 priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > q; //最小堆 for(auto it : map) if(q.size() == k) { //队列满了 if(it.second > q.top().first) { //堆排 q.pop(); q.push(make_pair(it.second, it.first)); } } else q.push(make_pair(it.second, it.first)); vector<int> res; while(q.size()) { //将优先队列中k个高频元素存入vector res.push_back(q.top().second); q.pop(); } return vector<int>(res.rbegin(), res.rend()); } };
