[leetcode]347.前k个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

思路：
hashmap+小顶堆。
首先使用hashmap统计每一个数出现的频率。
其次使用优先队列，原理类似在一个数组中找第k大的数，存入出现频率前k大的数。
最后将队列中所有元素出队，将其对应的值存入ans数组中，返回。

(优先队列中的数据结构使用pair，小根堆的优先队列默认以pair的第一个值排序，因此存入的都是<频率，值>.)
AC代码：（C++）

class Solution {
   public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
        vector<int> ans;
        for (int num : nums) {
            if (mp.find(num) != mp.end())
                mp[num]++;
            else
                mp[num] = 1;
        }
        unordered_map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++) {
            if (k == q.size()) {  //队列已满
                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));
            }
        }
        while (!q.empty()) {
            ans.push_back(q.top().second);
            q.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};