难度中等1472收藏分享切换为英文接收动态反馈
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
解题思路：优先级队列
很明显，这是一个 top K 问题，具体的可以看堆部分的知识笔记！
这里要求的是前 K 个高频元素，那么我们需要先用一个 unordered_map 来记录一下每个元素出现的次数，接着再通过优先级队列，遍历数组，并且固定 K 个元素存放在优先级队列中，最后再将优先级队列的数据放到 vector 中返回！
其中要注意的就是我们要前 K 个大的数，那么我们就要用小堆！也就是 greater（和我们平时使用习惯是相反的），但是由于我们用的是 unordered_map，其存放元素的是一个键值对也就是 pair<int, int>，所以我们要自己写一个仿函数或者lambda表达式，这里我们用仿函数，然后通过优先级队列的模板参数传递来完成定义这个小堆！
struct Compare
{
bool operator()(const pair<int, int>& m1, const pair<int, int>& m2)
{
return m1.second > m2.second;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 存放每个数字出现的频率
for(const auto& e : nums)
hash[e]++;
// 优先级队列默认是大堆，我们得让其变成小堆
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
auto it = hash.begin();
while(it != hash.end())
{
pq.push(*it);
if(pq.size() > k)
pq.pop();
++it;
}
vector<int> v;
while(!pq.empty())
{
v.push_back(pq.top().first);
pq.pop();
}
return v;
}
};