[LeetCode Hot 100] LeetCode347. 前K个高频元素-526互联

题目描述

思路：小顶堆

首先遍历整个数组，并是用哈希表记录每个数字出现的次数，并形成一个"出现次数数组"。
1. 找出原数组的前k个高频元素，就相当于找出"出现次数数组"的前K大的值。
建立一个小顶堆，然后遍历"出现次数数组"
1. 如果堆的元素个数小于k，就可以直接插入堆中。
2. 如果堆的元素个数等于k，则检查堆顶与当前值出现次数的大小。如果堆顶元素更大，说明至少有k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
遍历完成后，堆中的元素就代表了"出现次数数组"中前K大的值。

方法一：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 最小堆
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            (e1, e2) -> e1.getValue() - e2.getValue()
        );

        // 遍历每一个元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (heap.size() == k) {
                // 从第k+1个数开始，如果大于堆顶元素，就删除堆顶元素，并添加当前元素
                if (heap.peek().getValue() < entry.getValue()) {
                    heap.poll();
                    heap.offer(entry);
                }
            } else if (heap.size() < k){
                // 先将前k个元素加入小顶堆中
                heap.offer(entry);
            }
        }

        // 收集结果
        int[] res = new int[k];
        for (int i = 0; i < k; i ++) {
            res[i] = heap.poll().getKey();
        }
        return res;
    }
}