【20230401】【每日一题】前K个高频元素

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

• 统计元素出现的频率 ---用map
• 对出现的频率进行排序---优先级队列
• 找出前K个高频元素

优先级队列：披着队列外衣的堆

堆是一颗完全二叉树，树中每个节点的值都不小于（或不大于）其左右孩子的值。

大顶堆（堆头是最大元素）   小顶堆（堆头是最小元素）

priority_queue< type, container, function >

type：数据类型；
container：实现优先队列的底层容器；
function：元素之间的比较方式；
对于container，要求必须是数组形式实现的容器，例如vector、deque，而不能使list。
在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

class Solution {
public:
    class myCompare{
    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 num : nums){
            map[num]++;
        }
        //小顶堆
        priority_queue<pair<int,int>,vector<pair<int,int>>,myCompare> priority_que;
        //用固定大小k的小顶堆，扫描所有频率
        for(auto it=map.begin();it!=map.end();it++){
            priority_que.push(*it);
            if(priority_que.size()>k){
                priority_que.pop();//把小的弹出去
            }
        }
        vector<int> res(k);
        for(int i=k-1;i>=0;i--){
            res[i]=priority_que.top().first;
            priority_que.pop();
        }
        return res;
    }
};