347. 前 K 个高频元素

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;
    }
};

发表评论