Leetcode|堆|347. 前 K 个高频元素

1 堆—优先队列

时间复杂度：O(NlogK)

代码语言：javascript复制

class Solution {
public:
    class cmp {
        public:
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.second >= b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        unordered_map<int, int> val2cnt;
        for (auto& num : nums) val2cnt[num]  ;
        for (auto& [val, cnt] : val2cnt) {
            if (q.size() < k)
                q.emplace(val, cnt);
            else if (q.size() == k && cnt > q.top().second) {
                q.pop();
                q.emplace(val, cnt);
            }
        }
        vector<int> res;
        while (!q.empty()) {
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }
};

队列

0 人点赞