天涯岂是无归意
争奈归期未可期
C++，最小堆+hash。
说一个很多人不知道的小知识点，C++中不同pair之间大小比较默认先比较first，再比较second，这样对做这道题有帮助。如果没有pair这个特性的话，可能得写个struct进行重载或者自定义比较函数了。 思路也是很简单的，先用hash达到记录元素频次的目的，然后再用一个大小为K的最小堆，选出频次最高的K个元素，输出就好了。
思路可以整理一下：
- 用
unordered_map进频次统计 - 遍历
unordered_map，使用优先队列构造一个容量为K的最小堆- 优先队列使用
priority_queue<T, vector<T>, greater<T>> heap，其中T = pair<int, int> - 构造pair的时候记得频次在前，元素在后，因为pair默认先比较first，再比较second
- 把构造的pair按规则决定是否压入优先队列中
- 优先队列使用
- 输出优先队列
基于上述思路，就可以写出代码了。
class Solution {
public:
using T = pair<int, int>;
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for (const int &it : nums) hash[it]++;
priority_queue<T, vector<T>, greater<T>> heap;
for (auto &it : hash) {
T value = make_pair(it.second, it.first);
if (heap.size() >= k) {
if (it.second > heap.top().first) {
heap.pop();
heap.push(value);
}
} else heap.push(value);
}
vector<int> ans;
while (!heap.empty()) {
ans.push_back(heap.top().second);
heap.pop();
}
return ans;
}
};
