题目

给定一个非空数组，返回其中出现频率前K高的元素。
示例1：

输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]

示例2：

输入：nums = [1], k = 1
输出：[1]

思路

1. 首先，提到出现频率，就能想到，使用字典中key-value形式，当有重复关键字出现，value就加一。
2. 其次，本题要求返回出现频率前K高的元素，即需要对value进行排序，依次输出前k个。这恰好符合堆的性质。难点在于，怎么按map中的value值排序！
3. 本题使用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，将零碎时间利用起来】