力扣 347. 前 K 个高频元素

🔗 https://leetcode.cn/problems/top-k-frequent-elements

题目

• 给一个数组，返回其中出现频率前 K 高的数字

思路

• 统计数组中数字出现的频率
• 优先队列，建立大小为 k 的小根堆，根据数字出现的频率排序
• 更新并维护该优先队列，便是前 K 个高频元素

代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (auto num : nums) {
            m[num]++;
        }

        auto minHeapCompare = [](pair<int, int> left, pair<int, int> right) {
		return left.second > right.second; // 自定义比较器，建立最小堆
};
std::priority_queue<pair<int, int>, std::vector<pair<int, int>>, decltype(minHeapCompare)>
            heap(minHeapCompare);

        for (auto item : m) {
            if (heap.size() < k) {
                pair<int, int> p = make_pair(item.first, item. second);
                heap.push(p);
                continue;
            }
            if (item.second > heap.top().second) {
                heap.pop();
                pair<int, int> p = make_pair(item.first, item. second);
                heap.push(p);
            }

            
        }

        vector<int> ans;
        while (heap.empty() == false) {
            ans.push_back(heap.top().first);
            heap.pop();
        }
        return ans;
    }
};