【Day 20】347. 前 K 个高频元素.md

思路

先遍历数组，用哈希表记录每个数字出现的次数；

建立小根堆，遍历哈希表，如果堆的元素个数小于k，则直接插入堆中；

如果堆的元素个数等于k，则比较堆顶与当前出现次数的大小，如果当前的更大，则弹出堆顶，将其插入堆中，否则继续遍历；

遍历结束，堆中元素即为所求目标。

代码

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

        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

复杂度分析

• 时间复杂度：O(nlogk)，遍历数组建立哈希表是O(n)，遍历哈希表进行小根堆的维护是O(nlogk)。
• 空间复杂度：O(n)，哈希表大小O(n)，小根堆O(k)。