347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
这道题要求我们在O(n log n)的时间复杂度内，返回一个数组中出现次数最多的k个元素，要求复杂度小于O(nlogn)，这道题的难度主要在时间复杂度的要求比较严格上，思路如下:
哈希表+堆
这道题可以转化为对数组中各个元素的出现次数进行统计，之后从这个次数的序列中找到前k大的元素，那么要解决寻找前k大的元素的问题，我们有了之前的经验，应该选用堆这种数据结构，而且应该是小顶堆。
确定前k大的元素的思路和378. Kth Smallest Element in a Sorted Matrix基本一致，代码上稍作了一些修改，代码如下:
时间复杂度为O(nlogk)
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hash;
vector<int> res;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;/*第一个参数指定元素类型，第二个参数决定使用哪一种容器，
第三个用于建立小顶堆*/
for(auto num:nums)
hash[num]++;
for(auto pos : hash){
heap.push({pos.second,pos.first});
if(heap.size()>k)
heap.pop();
}
while(!heap.empty()){
res.push_back(heap.top().second);
heap.pop();
}
return res;
}
};