LeetCode 347. 前 K 个高频元素

347. 前 K 个高频元素

解题思路

构建小根堆，堆顶元素为当前出现频率最低的元素，当堆中元素个数超过 k 时，弹出堆顶元素。最后堆中剩余的 k 个元素即为出现频率最高的 k 个元素。

参考代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];

        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(
            (a, b) -> a.getValue() - b.getValue()
        );

        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.add(entry);
            if(queue.size() > k) {
                queue.poll();
            }
        }

        for(int i = 0; i < k; i ++) {
            res[i] = queue.poll().getKey();
        }
        return res;
    }
}