力扣题目链接
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 \(O(n\log n)\) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
这道题目有三个要素：
- 要统计元素出现频率（map）
- 对频率排序
- 找出前k个高频元素
重点在如何对频率排序的同时找出前k个高频元素，同时保证算法时间复杂度不高于 \(O(n\log n)\)；
优先级队列
一种容器适配器stl；优先级队列是一个披着队列外衣的堆，使用起来的感觉是从队头取元素，队尾添加元素，其内部自动依照元素的权值排列；
如何做到有序排列的？
缺省情况下priority_queue利用max_heap完成对元素的排列，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
*：什么是堆？
堆是一种完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值；
本题使用优先级队列最优；
而且由于这道题要求留下高频去掉低频的，因此我们利用小根堆每次都去除留下的最小值的性质，进行排序；
其中小根堆代码：
priority_queue<元素类型, 底层容器, 比较器> 变量名;
比较器，缺省默认大根堆，小根堆改变比较器：
class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};
然后改为：
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
其中要注意遍历map需要使用迭代器unordered_map<pair<int,int>>::iterator it，并且最后倒序输出到vector<int> result中；
具体代码如下：
```cpp
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;//key-nums[i],value-timesfor(int i = 0; i < nums.size();i++){map[nums[i]]++;}priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> 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;}
};