📃 题目描述

题目链接：

• 347. 前 K 个高频元素 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 剑指 Offer II 060. 出现频率最高的 k 个数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

🔔 解题思路

经典 TopK 问题

在面试过程中遇到这个题目，首先要想到的是解决这个题目需要用到哈希表。这个题目的输入是一个数组，哈希表可以用来统计数组中数字出现的频率，哈希表的键是数组中出现的数字，而值是数字出现的频率

接下来找出出现频率最高的 k 个数字，可以使用小根堆，每次弹出堆顶元素（出现频率最低的元素），直到堆中留下的元素个数为 k 个，就是出现频率前 k 高的元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return new int[0];
        }

        // 存储最终结果
        int[] res = new 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>> minHeap = new PriorityQueue<>(
                (o1, o2) -> o1.getValue() - o2.getValue()
        );
        // 等价于
        // PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
        //     new Comparator<Map.Entry<Integer, Integer>>() {
        //         @Override
        //         public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
        //             return o1.getValue() - o2.getValue();
        //         }
        //     }
        // );
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }

            else {
                if (entry.getValue() > minHeap.peek().getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }

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

只用哈希表也能做这道题，不过相对来说考虑的东西会多一点

💥 复杂度分析

• 时间复杂度：O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(N) 的时间。随后，我们遍历哈希表构造小顶堆，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间。二者之和为 O(Nlogk)
• 空间复杂度：O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)