347.前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 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;
};