9/7刷题前 K 个高频元素

1.前 K 个高频元素

思路一：小顶堆

优先队列的使用https://www.cnblogs.com/huashanqingzhu/p/11040390.html

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;//小顶堆，升序排列
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for (auto& v : nums) {
            occurrences[v]++;
        }

        // 优先队列，pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for (auto& [num, count] : occurrences) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }//等于k了，一个一个进行对比，如果里面最小的小于新的值，就把最小的放入
            } else {
                q.emplace(num, count);
            }//小于k就按照规则依次放入
        }
        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};