347. 前 K 个高频元素

这个题用到了小顶堆，之前用的比较少所以记录一下。

priority_queue 优先队列

C++实现堆有现成的容器适配器：priority_queue。

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

写一个自定义operator构造小顶堆的例子，注意小顶堆是用greater：

priority_queue<int, vector<int>, greater<int> > q;
for( int i= 0; i< 10; ++i ) q.push(10-i);
while( !q.empty() ){
    cout << q.top() << endl;
    q.pop();
}
输出如下：
1
2
3
4
5
6
7
8
9
10

自定义一个pair类型的小顶堆：

#include<iostream>
#include <queue>

using namespace std;
class mycomparison {
public:
    bool operator() (const pair<int,int>& lhs,const pair<int,int>& rhs){
        return lhs.second>rhs.second;
    }
};

int main(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> que;
    que.push({1,2});
    que.push({1,7});
    que.push({2,4});
    while (!que.empty()){
        cout<<que.top().second<< endl;
        que.pop();
    }
}

输出：
2
4
7

题解

这个题首先用hash表记录每个数字出现的频率，然后维护一个大小为k的小顶堆（因为最后要留下最大的k个元素，小顶堆每次把小的元素弹出，留下的就是最大的k个了），最后把小顶堆的元素倒序输出即可。

class Solution {
public:
    class mycomparison {
        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]]++;
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>,mycomparison>priority_que;

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

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