【LeetCode 27】347.前k个高频元素

class Solution {
public:
    //小顶堆
    class mycomparision{
        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> map;
        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]]++;
        }
        //对元素出现的次数进行排序
        //定义一个小顶堆，大小为k
        priority_queue<pair<int,int>,vector<pair <int,int>>,
        mycomparision>pri_que;
        //用固定大小为k的小顶堆遍历所有元素出现次数的整数值
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++)
        {
            pri_que.push(*it);
            if(pri_que.size()>k)//如果堆的大小大于k，则队列弹出，保证堆的大小一直为k
            {
                pri_que.pop();
            }
        }
        //找出前k个高频元素，因为小顶堆先弹出的是最小的元素，所以倒序输出列result
        //数组中
        vector<int> result (k);
        for(int i=k-1;i>=0;i--)
        {
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};