题意

给一个序列, 输出其前K个出现频次的数字

方法

优先队列

代码

class Solution {
public:
    struct node{
        int val;//值
        int cnt;//出现次数
        node():cnt(0){}
        node(int aval , int acnt):val(aval),cnt(acnt){}
    };//构造计数节点
    class Comp{
        public:
        bool operator()(node a , node b){
            return a.cnt < b.cnt;
        }
    };//自定义comp
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<node,vector<node>,Comp> pq;
        sort(nums.begin() , nums.end());//先排序保证计数的连贯性
        vector<node> temp;temp.emplace_back(nums[0] , 1);//这里先手传值，也可以放到for里
        int n = nums.size();
        for(int i = 1 ; i < n ;i++){
            if(nums[i] == nums[i - 1]){
                temp.back().cnt++;
            }else {
                temp.emplace_back(nums[i] , 1);
            }
        }
        while(!temp.empty()){
            pq.push(temp.back());
            temp.pop_back();
        }//将各个节点放进优先队列里
        vector<int> res;
        while(k > 0){
            res.push_back(pq.top().val);
            pq.pop();
            k--;
        }
        return res;
    }
};