【LeetCode 热题 100】347. 前 K 个高频元素——（解法三）桶排序

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

整体思路

这段代码同样旨在解决 “前 K 个高频元素” 问题。它采用了一种非常巧妙且在特定情况下极为高效的 桶排序 策略。这种方法的时间复杂度可以达到线性级别，是此问题的一个重要优化方向。

算法的整体思路可以分解为以下三个步骤：

1. 第一步：频率统计

   • 与之前的所有方法一样，算法首先使用一个 哈希表 (HashMap) frequencyMap 来高效地统计数组 nums 中每个数字出现的频率。
   • 这是后续桶排序的基础。

2. 第二步：桶排序——按频率分桶

   • 这是算法的核心。它创建了一个“桶”数组 buckets。
   • 桶的定义：buckets 是一个列表数组，buckets[i] 这个“桶”被设计用来存储所有出现频率恰好为 i 的数字。
   • 桶的大小：数组的长度设置为 nums.length + 1，因为一个数字的出现频率最高不可能超过 nums 的总长度 n。
   • 装桶：算法遍历 frequencyMap 中的每一个键值对（{数字, 频率}）。对于一个条目 {num, freq}，它将 num 放入索引为 freq 的那个桶中，即 buckets[freq].add(num)。
   • 这一步结束后，所有数字都被按照它们的出现频率分门别类地放进了不同的桶里。

3. 第三步：逆序提取结果

   • 由于 buckets 数组的索引本身就代表了频率，并且是天然有序的，所以我们不再需要进行任何显式的排序操作。
   • 算法从 buckets 数组的末尾（即最高频率）开始向前遍历。
   • 对于每个非空的桶 buckets[i]，它里面的所有数字都是当前能找到的频率最高的数字。
   • 将这些桶里的数字依次填入结果数组 ans 中，直到填满 k 个元素为止。
   • 返回 ans 数组。

这种方法用空间换时间，通过创建一个与频率范围相关的桶结构，巧妙地规避了基于比较的排序（如 O(M log M) 或 O(M log k)），从而实现了线性时间的解决方案。

完整代码

class Solution {
    /**
     * 找出数组中出现频率最高的前 k 个元素。（桶排序法）
     * @param nums 整数数组
     * @param k 需要找出的元素个数
     * @return 包含前 k 个高频元素的数组
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 步骤 1: 使用 HashMap 统计每个数字的出现频率
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 步骤 2: 创建桶，并按频率将数字放入相应的桶中
        // 桶的索引代表频率，桶的内容是具有该频率的数字列表
        // 数组长度为 nums.length + 1，因为频率最高为 nums.length
        List<Integer>[] buckets = new ArrayList[nums.length + 1];

        // 初始化每个桶为一个空的 ArrayList
        Arrays.setAll(buckets, i -> new ArrayList<>());
        
        // 遍历频率 map，将数字放入对应的频率桶
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            buckets[entry.getValue()].add(entry.getKey());
        }

        // 步骤 3: 从后向前（从高频率到低频率）遍历桶，提取前 k 个元素
        int j = 0; // ans 数组的指针
        int[] ans = new int[k];
        // 从最高频率的桶开始遍历
        for (int i = nums.length; i >= 0 && j < k; i--) {
            // 如果当前频率的桶不为空
            if (!buckets[i].isEmpty()) {
                // 将该桶中的所有数字加入结果数组
                for (int num : buckets[i]) {
                    ans[j++] = num;
                    // 如果已经找到了 k 个，可以提前终止
                    if (j == k) {
                        break;
                    }
                }
            }
        }
        return ans;
    }
}

时空复杂度

时间复杂度：O(N)

1. 频率统计：遍历 nums 数组一次，填充哈希表。时间复杂度为 O(N)。
2. 装桶：遍历 frequencyMap 一次。map 中最多有 N 个条目（最坏情况下是 M=N）。此步骤时间复杂度为 O(M)，其中 M 是唯一元素的数量。
3. 提取结果：
   • 外层 for 循环从 nums.length 遍历到 0，执行 N+1 次。
   • 内层 for 循环遍历桶中的数字。虽然有嵌套循环，但每个唯一数字 num 只会被装入一个桶，也只会被从桶中提取一次。因此，所有内层循环的总执行次数等于唯一元素的数量 M。
   • 所以，提取结果的总时间复杂度为 O(N) (外层循环) + O(M) (所有内层循环) = O(N)。

综合分析：
总时间复杂度 = O(N) (统计) + O(M) (装桶) + O(N) (提取)。
由于 M <= N，所以总的时间复杂度可以简化为 O(N)。这是解决此问题的最优时间复杂度。

空间复杂度：O(N)

1. 主要存储开销：
   • HashMap frequencyMap: 需要存储所有 M 个唯一元素及其频率。空间为 O(M)。
   • List<Integer>[] buckets: 这是一个长度为 N+1 的数组，它存储了所有 M 个唯一数字。所以 buckets 数组本身的大小是 O(N)，其内部所有 ArrayList 存储的元素总数是 M。因此，这部分占用的总空间是 O(N + M)。

综合分析：
算法所需的额外空间由哈希表和桶数组共同构成。总的空间复杂度为 O(M) + O(N + M) = O(N + M)。由于 M <= N，可以简化为 O(N)。

参考灵神