Leetcode 347.前 K 个高频元素（画图分析）

力扣传送门(opens new window)

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

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路：

• 借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
• 维护一个元素数目为 k 的最小堆
• 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
• 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
• 最终，堆中的 k 个元素即为前 k 个高频元素

具体步骤如下：

1. 创建一个 HashMap（哈希表），用于统计每个数字出现的频率。键为数字，值为对应数字的出现次数。
2. 首先，检查给定的数组 nums 是否为空或长度为0。如果是，直接返回一个空数组，因为没有元素可以进行统计。
3. 遍历 nums 数组，对每个数字进行统计。对于数组中的每个数字：
   • 如果该数字不在哈希表中，将其添加到哈希表，并将其出现次数初始化为1。
   • 如果该数字已经在哈希表中，将其出现次数加1。
4. 创建一个优先队列（最小堆）来保存出现频率最大的k个元素。优先队列中的元素将按照频率进行排序，频率最小的元素在队列的头部。
5. 遍历哈希表中的每个数字和对应的频率：
   • 如果优先队列的大小小于k，直接将当前数字加入队列。
   • 如果当前数字的频率大于队列中最小频率的数字，则将最小频率的数字出队，将当前数字入队，确保队列中始终保持出现频率最大的k个元素。
6. 最后，将优先队列中的元素取出，并将它们放入结果数组中。由于优先队列是最小堆，所以取出的元素会按照频率从小到大排列。
7. 返回结果数组作为最终的答案。

代码实现：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap();
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的频率
        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])) {
                hashMap.put(nums[i], 1);
            } else {
                hashMap.put(nums[i], hashMap.get(nums[i]) + 1);
            }
        }

        // 使用优先队列（最小堆）来保存出现频率最大的k个元素
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            return hashMap.get(o1) - hashMap.get(o2);
        });

        // 遍历哈希表中的每个数字
        for (Integer key : hashMap.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
            } else if (hashMap.get(key) > hashMap.get(queue.peek())) {
                // 如果当前数字的频率大于队列中最小频率的数字，则将最小频率的数字出队，将当前数字入队
                queue.remove();
                queue.add(key);
            }
        }
  
        // 将最小堆中的元素取出并放入结果数组
        int[] res = new int[queue.size()];
        int index = 0;
        while (!queue.isEmpty()) {
            res[index++] = queue.poll();
        }
        return res;
    }
}