博客

前言

题目描述

给定一个非空的整数数组，返回其中出现频度前K高的元素

题目解析

首先这道题很容易理解，就是说你要找到一种方法，来统计给定数组中出现的元素以及其出现的频度，然后返回前K个高频元素即可，如果频度相同那就返回元素值比较大的元素。

解题思路

（1）首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个【出现次数数组】

（2）找到原数组的前K个高频元素，就相当于找出【出现次数数组】的qianK大的值

最简单的做法就是给【出现次数数组】排序，但由于可能给有N个不同的出现次数，所以总的算法复杂度会达到NlogN，不满足题目的要求。

在这里，我们可以借助堆的思想：


建立一个小顶堆


，然后遍历【出现次数数组】

（1）如果堆的元素个数小于K，就可以将元素直接插入到堆中

（2）如果堆的元素个数等于K，则检查堆顶与当前出现次数的大小。如果堆顶更大，就说明至少有k个数字的出现次数比当前值大，所以直接舍弃当前【出现次数数组】的值；否则就弹出堆顶，并将当前值插入堆中。

遍历完之后，堆中的元素就代表了【出现次数数组】中前k大的值。

代码

vector<int> topKFrequent(vector<int> &nums,int k){
	unordered_map<int,int> occurrences;//构造哈希表，存放元素以及其出现的次数
	for(int nu:nums){
		occurrences[nu]++;
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp);
	for(auto iter=occur.begin();iter!=occur.end();iter++){
		if(q.size()==k){//如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小
			if(q.top().second<iter->second){ //如果堆顶更小，则弹出堆顶，将当前大的值插入堆中
				q.pop();
				q.emplace(iter->first,iter->second);
			}
		}
		else{//如果堆的元素个数小于 kk，就可以直接插入堆中
			q.emplace(iter->first,iter->second);
		}
	}
	vector<int> res;
	while(!q.empty()){
		res.emplace_back(q.top().first);
		q.pop();
	}
	reverse(res.begin(), res.end());//逆置，因为是小顶堆，次数小的在堆顶，所以在输出的时候要从下往上输出，逆置一下即可
	return res;
}

//比较函数
statcic bool cmp(pair<int,int> &m,pair<int,int> &n){
	return m.second>n.second;
}

代码中出现了很多我之前并没有接触过的东西，现在在这里

补充

：

小顶堆补充知识

小顶堆的声明和使用


强烈建议看这个链接

首先是小顶堆的创建：

在上一节中，我们知道优先队列其实和大顶堆是一个概念，也就是大顶堆可以直接用priority_queue max_heap;

但是小顶堆需要我们重新声明：

priority_queue< int,vector,greater > min_heap;

其中第一个元素类型int表示我们小顶堆中存放的数据类型，第二个参数是容器的类型，第三个参数是比较函数。

因为我们在这里用小顶堆比较的不只有次数，还有元素的大小，所以一般我们用[pair对组]

对组详解

(https://www.cnblogs.com/cszlg/archive/2013/03/10/2952807.html)（可以简单的认为是字典形式）来表示小顶堆，即：

priority_queue< pair<int,int>,vector<pair<int,int>>,比较函数 >

关于大小顶堆的比较函数：

看这里

我们还注意到代码中的比较函数cmp前面有一个

decltype关键字

：

之前没有见过，今天来学习一下：

decltype关键字被称作类型说明符，它的作用是选择并返回操作数的数据类型

比如：decltype(f()) sum=x;//sum的类型就是函数f返回的类型

decltype可以作用于变量、表达式及函数名。①作用于变量直接得到变量的类型；②作用于表达式，结果是左值的表达式得到类型的引用，结果是右值的表达式得到类型；③作用于函数名会得到函数类型，不会自动转换成指针。

完整代码

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<array>
#include<algorithm>
using namespace std;

class Solution{
	public:
		
		static bool cmp(pair<int,int> &m,pair<int,int> &n){
			return m.second>n.second;
		}
		vector<int> topKFrequent(vector<int> &nums,int k){
			unordered_map<int,int> occur;
			for(int v:nums){
				occur[v]++;
			}
			priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> q(cmp);//建立小顶堆 
			for(auto iter=occur.begin();iter!=occur.end();iter++){
				if(q.size()==k){//如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小
					if(q.top().second<iter->second){ //如果堆顶更小，则弹出堆顶，将当前大的值插入堆中
						q.pop();
						q.emplace(iter->first,iter->second);
					}
				}
				else{//如果堆的元素个数小于 kk，就可以直接插入堆中
					q.emplace(iter->first,iter->second);
				}
			}
			vector<int> res;
			while(!q.empty()){
				res.emplace_back(q.top().first);
				q.pop();
			}
			reverse(res.begin(), res.end());
			return res;
		}
};


int main(){
	int len;
	cin>>len;
	vector<int> nums;
	int n=0;
	int data;
	while(n<len && cin>>data){
		n=n+1;
		nums.push_back(data);
	}
	int k;
	cin>>k;
	vector<int> res=Solution().topKFrequent(nums,k);
	for(int i=0;i<res.size();i++){
		if(i>0){
			cout<<" ";
			
		}
		cout<<res[i];
	}
	return 0;
}