347. 前 K 个高频元素 - 力扣（LeetCode）

首先想到哈希，用key来存元素，value来存出现次数，最后进行排序，时间复杂度约为o(nlogn)。由于只需求前k个，因此可以进行优化，利用堆来维护这k个元素，由于最终要剩下k个最大的元素，因此元素每次加入堆时，要将堆中最小元素弹出，因此要用小根堆来维护。

class Solution {
public:
    class MinHeapComparator {
    public:
    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> hash; //哈希表

        for(int i = 0; i < nums.size(); i++){
            hash[nums[i]]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, MinHeapComparator> minheap;

        for(auto item : hash){//将哈希表元素加入堆中
            minheap.push(item);
            if(minheap.size() > k){
                minheap.pop();
            }
        }

        vector<int> res(k);//存前k个高频元素
        
        for(int i = k-1; i >= 0; i--){//由于是小根堆，因此倒序存在res中
            res[i] = minheap.top().first;
            minheap.pop();
        }

        return res;
            
    }
};