给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
class cmp
{
public:
bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
return a.second > b.second;
}
//由于每次出队的时候都是将最小的元素和最后一个元素互换，导致形成小顶堆
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
for (const auto &i : nums)
{
mp[i]++;
}
std::priority_queue<std::pair<int,int>,vector<std::pair<int, int>>,cmp> que;
//维护一个只有k个元素的小顶堆
for (auto it = mp.begin();it!=mp.end();it++)
{
if (que.size() == k)
{
que.push(*it);
que.pop();
}
else
{
que.push(*it);
}
}
//将最后小顶堆中的元素倒序输出即为res
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = que.top().first;
que.pop();
}
return result;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
for (const auto &i : nums)
{
mp[i]++;
}
vector<std::pair<int, int>> vec;
for (const auto& item : mp)
{
vec.emplace_back(item);
}
std::sort(vec.begin(), vec.end(),
[](const auto& x, const auto& y)->bool {return x.second > y.second; });
vec.resize(k);
for (const auto& item : vec)
{
res.emplace_back(item.first);
}
return res;
}
private:
std::unordered_map<int, int> mp;
};