LeerCode 前 K 个高频元素（优先级队列）

用unordered_map统计每个数的频率，然后用优先级队列大顶堆排序，取出前K个即可

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // pair
        unordered_map<int, int> mp;
        for (int num : nums) {
            mp[num]++;
        }
        auto mycmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs)->bool {
            return lhs.second < rhs.second;
        };
        using MaxHeap = priority_queue < pair<int, int>, vector<pair<int, int>>, decltype(mycmp)>;
        MaxHeap maxHeap(mycmp);
        for (auto it = mp.begin(); it != mp.end(); it++) {
            maxHeap.push(*it);
        }
        vector<int> ans;
        for (int i = 0; i < k; i++) {
            ans.push_back(maxHeap.top().first);
            maxHeap.pop();
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

priority_queue < pair<int, int>, vector<pair<int, int>>, decltype(mycmp)> maxHeap(mycmp);
1

第三个模板参数必须是class，需要用decltype推导，然后给构造函数传入用于比较的函数对象

class Solution {
public:
    class mycomparison {
        public:
            bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
                return lhs.second < rhs.second;
            }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        // num, freq
        unordered_map<int, int> mp;
        for (int num : nums) {
            mp[num]++;
        }
        
        priority_queue < pair<int, int>, vector<pair<int, int>>, mycomparison> maxHeap;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            maxHeap.push(*it);
        }
        vector<int> ans;
        for (int i = 0; i < k; i++) {
            ans.push_back(maxHeap.top().first);
            maxHeap.pop();
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

自己手写比较类mycomparison时，直接传入模板参数即可