前 K 个高频元素 图解题解

import heapq
from collections import Counter
cnt = Counter(nums)            # 数次数，同桶法第一步
heap = []                      # 大小<=k 的小顶堆，存 (次数, 数)
for x, c in cnt.items():
    heapq.heappush(heap, (c, x))
    if len(heap) > k:          # 超过 k 个就弹掉堆顶(当前最低频)
        heapq.heappop(heap)
return [x for c, x in heap]    # 堆里剩下的就是前 k 高频，O(n log k)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        for (int x : nums) cnt[x]++;        // 数次数
        // 小顶堆：pair<次数, 数>，按次数从小到大，堆顶=当前最低频
        priority_queue<pair<int,int>, vector<pair<int,int>>,
                       greater<>> heap;
        for (auto& [x, c] : cnt) {
            heap.push({c, x});
            if ((int)heap.size() > k) heap.pop();  // 超 k 弹堆顶
        }
        vector<int> ans;
        while (!heap.empty()) { ans.push_back(heap.top().second); heap.pop(); }
        return ans;                          // O(n log k)
    }
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.merge(x, 1, Integer::sum);  // 数次数
        // 小顶堆：按次数升序，堆顶=当前最低频；只留 k 个
        PriorityQueue<int[]> heap =
            new PriorityQueue<>((a, b) -> a[1] - b[1]);   // a=[数, 次数]
        for (Map.Entry<Integer,Integer> e : cnt.entrySet()) {
            heap.offer(new int[]{e.getKey(), e.getValue()});
            if (heap.size() > k) heap.poll();             // 超 k 弹堆顶
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = heap.poll()[0];
        return ans;                                       // O(n log k)
    }
}