347.前 K 个高频元素

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

示例 1:

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

这道题看似很简单，理解起来也容易，但真正敲代码时会牵涉到很多知识点。

基本思路就是：

1.记录元素出现频率

2.对出现频率排序

3.输出频率大于k的元素

开始干！

1.统计频率用的当然是哈希表啦

unordered_map<int,int> map;
        for(int x:nums){
            map[x]++;
        }

这个不用多说，关于哈希表，可以看哈希表总结这篇文章

2.关于排序，这时候可以讲到本篇文章的重点：优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

可以理解为大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。

C++用专门的数据结构：priority_queue（优先级队列），底层实现是大顶堆和小顶堆。

定义

priority_queue<Type, Container, Functional>;

Type是要存放的数据类型

Container是实现底层堆的容器，必须是数组实现的容器，如vector、deque

Functional是比较方式/比较函数/优先级

priority_queue<Type>;

此时默认的容器是vector，默认的比较方式是大顶堆less<type>

举例

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//大顶堆
priority_queue <int,vector<int>,less<int> >q;
//默认大顶堆
priority_queue<int> a;

对于本题，要设定比较规则，以制造小顶堆：

class mycompairison{
        public:
        bool operator()(const pair<int,int>& left,const pair<int,int>& right){
            return left.second>right.second;//小顶堆
        }

在这个函数签名中，operator() 是一个函数调用运算符的重载。在 C++ 中，当类中定义了 operator() 函数时，这个类的实例就可以像函数一样被调用。

pair 是 C++ 标准库中的一个模板类，用于将两个值组合成一个单元，这两个值可以是不同类型的。它通常用于需要将两个值作为一个单元处理的情况，例如在排序算法中使用自定义比较函数对键值对进行排序，或者在哈希表中存储键值对等。

在设定好排序规则后，就可以调用了。

priority_queue<int,vector<pair<int,int>>,mycompairison> pri_que;

接下来利用迭代器把map塞到我们的小顶堆中。

for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k){//把顶端（最小值）弹出
                pri_que.pop();
            }
        }

最后就可以输出了，注意是要倒序输出给数组，因为要先弹出小的。

vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }

真是一场酣畅淋漓的解题，总体代码如下：

class Solution {
private:
    class mycompairison{
        public:
        bool operator()(const pair<int,int>& left,const pair<int,int>& right){
            return left.second>right.second;//小顶堆
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(auto& x:nums){
            map[x]++;
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,mycompairison> pri_que;
        
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k){
                pri_que.pop();
            }
        }

        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};