前K个高频元素

前K个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素，示例如下：

本题涉及三个内容：

1.对数组元素出现的频率进行统计；

2.对频率进行排序；

3.找出前k个高频的元素。

解决方法：

1.实现频率统计可以使用map；

2.实现频率排序可以使用优先级队列实现。

优先级队列是披着队列外衣的堆，因为优先级队列对外接口只能是从头取元素和从队尾添加元素，优先级队列的内部元素自动按照权值进行排列，缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

本题使用小顶堆，每次将最小元素d出，最后积累的才是前k个最大元素。

3.找出前k个高频元素：根据出现频率构建map，构建小顶堆，如果堆的大小大于K就d出元素。

具体代码如下：

//前k个高频元素
//小顶堆
class mycomparison {
	public:
		bool operator() (const pairlhs, const pairrhs) {
			return lhs.second > rhs.second;
		}
}; 
 
vector topKFrequent(vector& nums, int k) {
	//统计元素出现的频率
	unordered_map map;
	for(int i = 0; i, vector>, mycomparison> pri_que;
	for (unordered_map::iterator it = map.begin(); it!=map.end(); it++) {
		pri_que.push(*it);
		if(pri_que.size() > k) {
			pri_que.pop();
		}
	} 
    vector result(k);
    for (int i = k-1; i>=0; i--) {
    	result[i] = pri_que.top().first;
    	pri_que.pop();
	}
	return result;
}