347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

示例 2:

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

使用哈希表做映射，将 map 中的键值对转移到一个向量 pairs 中进行排序：

class Solution {
public:
    static bool compare(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // 按照频率降序排序
    }   

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(auto& num : nums){
            if(map.find(num) != map.end()){
                map[num] += 1;
            }else{
                map[num] = 1;
            }
        }
        vector<pair<int, int>> pairs;
        for(auto& entry : map){
            pairs.push_back(entry);
        }
        // sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        //     return a.second > b.second;
        // }); // lambda表达式
        sort(pairs.begin(), pairs.end(), this->compare);
        vector<int> result;
        for(int i = 0; i < k && i < pairs.size(); i++){
            result.push_back(pairs[i].first);
        }
        return result;
    }
};

使用优先级队列来创建一个小顶堆：

class Solution {
public:
    struct mycomparison {
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
            }
    };   

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for(auto& num: nums){
            map[num]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        for(auto& entry: map){
            pri_que.push(entry);
            if(pri_que.size() > k){ // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }
        vector<int> result;
        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        for(int i = k - 1; i >= 0; i--){
            result.push_back(pri_que.top().first);
            pri_que.pop();
        }
        return result;
    }
};