Top K 频繁元素：桶排序算法深度解析与实现要点

本文深入探讨了如何使用桶排序算法高效解决“top k 频繁元素”问题。文章首先概述了问题背景，随后详细阐述了通过哈希表统计元素频率，再结合桶排序将元素按频率分组的核心思路。特别强调了在构建频率桶时，遍历哈希表的键集（`keyset()`）而非原始数组（`nums`）的重要性，以确保桶中存储的元素是唯一的。最后，提供了完整的 java 解决方案代码及详细解析，并总结了关键实现要点。

引言：理解 Top K 频繁元素问题

“Top K 频繁元素”是一个常见的算法问题，要求从一个整数数组中找出出现频率最高的 K 个元素。例如，给定数组 [1,1,1,2,2,3] 和 K=2，我们期望的输出是 [1,2]，因为 1 出现了 3 次，2 出现了 2 次，它们是频率最高的两个元素。解决这类问题通常需要高效地统计元素频率，并在此基础上进行排序或选择。

核心思路：频率统计与桶排序

解决“Top K 频繁元素”问题的一个高效方法是结合使用哈希表进行频率统计和桶排序（Bucket Sort）进行元素分组。

第一步：使用哈希表统计元素频率

首先，我们需要遍历输入数组 nums，统计每个元素出现的次数。哈希表（HashMap 在 Java 中）是实现这一目标的理想数据结构，它的键（Key）存储数组中的元素，值（Value）存储该元素的出现频率。

// the frequency of each element stored in map.
var map = new HashMap();
for(int n : nums) {
    map.put(n, map.getOrDefault(n, 0) + 1);
}

这段代码遍历 nums 数组，对于每个元素 n，如果它已存在于 map 中，则将其频率加 1；否则，将其添加到 map 中，并将频率初始化为 1。

第二步：构建频率桶

在统计完所有元素的频率后，我们可以创建一个“桶”数组。这个桶数组是一个 List[] 类型，其中数组的索引代表元素的频率，而该索引处存储的 List 则包含所有具有该频率的元素。例如，bucket[3] 将是一个列表，其中包含所有出现了 3 次的元素。桶数组的大小通常为 nums.length + 1，因为元素的最高频率不会超过数组的长度。

List[] bucket = new ArrayList[nums.length + 1];

关键抉择：遍历 keySet() 与遍历原始数组 nums 的区别

在将元素放入频率桶时，一个常见的疑问是：应该遍历哈希表的键集（map.keySet()）还是原始数组（nums）？这正是本问题中的核心困惑点。

为什么选择 map.keySet()

正确的做法是遍历 map.keySet()。map.keySet() 返回的是哈希表中所有唯一键的集合。这意味着我们只会处理每个不同的元素一次。

通义千问

阿里巴巴推出的全能AI助手

下载

for(int n : map.keySet()) {
    int freq = map.get(n); // 获取元素 n 的频率
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList();
    }
    bucket[freq].add(n); // 将元素 n 添加到对应频率的桶中
}

通过这种方式，每个唯一的元素 n 会被精确地放入它对应的频率桶中。例如，如果数字 1 出现了 3 次，它会且仅会出现在 bucket[3] 中一次。

为什么不能直接遍历 nums

如果选择遍历原始数组 nums 来填充桶，将会导致错误的结果。

// 错误示例：
for(int n : nums) {
    int freq = map.get(n);
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList();
    }
    bucket[freq].add(n); // 问题：同一个元素 n 会被多次添加到桶中
}

考虑数组 [1,1,1,2,2,3]。 当 n 是第一个 1 时，freq 为 3，1 被添加到 bucket[3]。 当 n 是第二个 1 时，freq 仍为 3，1 再次被添加到 bucket[3]。 当 n 是第三个 1 时，freq 仍为 3，1 第三次被添加到 bucket[3]。 最终，bucket[3] 中会包含 [1, 1, 1]。

然而，我们希望的是 bucket[3] 只包含一个 1，因为 1 是一个独立的元素，其频率为 3。问题的要求是找出“Top K 频繁元素”，这些元素本身应该是独特的。如果桶中包含重复的元素，那么在后续从桶中收集结果时，for(int element : bucket[i]) 循环将会把这些重复的元素也添加到最终结果中，导致输出不正确（可能包含重复元素或超出 K 个元素）。

完整 Java 解决方案详解

结合上述思路，以下是解决“Top K 频繁元素”问题的完整 Java 解决方案：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 初始化频率桶数组。
        // 数组索引代表频率，List 存储具有该频率的元素。
        // 最大频率不会超过 nums.length，所以大小为 nums.length + 1。
        List[] bucket = new ArrayList[nums.length + 1];

        // 2. 使用 HashMap 统计每个元素的频率。
        var map = new HashMap();
        for(int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // 3. 遍历 HashMap 的键集，将每个唯一的元素放入其对应频率的桶中。
        for(int n : map.keySet()) {
            int freq = map.get(n); // 获取元素 n 的频率
            if(bucket[freq] == null) {
                bucket[freq] = new ArrayList();
            }
            bucket[freq].add(n); // 将元素 n 添加到 bucket[freq] 列表中
        }

        // 4. 从高频率到低频率遍历桶，收集 Top K 频繁元素。
        int[] res = new int[k];
        int resIndex = 0; // 结果数组的当前填充位置
        int counter = 0;  // 已收集到的频繁元素数量

        // 从 bucket 数组的末尾（最高频率）开始向前遍历
        for(int i = bucket.length - 1; i >= 0; i--) {
            if(bucket[i] != null) { // 如果当前频率的桶不为空
                for(int element : bucket[i]) { // 遍历桶中的所有元素
                    res[counter++] = element; // 将元素添加到结果数组
                    if(counter == k) { // 如果已收集到 K 个元素，则返回结果
                        return res;
                    }
                }
            }
        }
        return res; // 理论上不会执行到这里，因为题目保证 K 是有效的
    }
}

代码解析：

1. List[] bucket = new ArrayList[nums.length + 1];: 初始化一个 ArrayList 数组作为桶。数组的每个位置 i 将存储一个 ArrayList，其中包含所有频率为 i 的元素。
2. var map = new HashMap();: 创建哈希表 map，用于存储 元素 -> 频率 的映射。
3. for(int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);: 遍历输入数组 nums，计算每个元素的频率并存储在 map 中。
4. for(int n : map.keySet()) { ... }: 这是关键步骤。 遍历 map 的键集，即所有不同的元素。对于每个元素 n，获取其频率 freq，然后将其添加到 bucket[freq] 对应的列表中。这一步确保了每个唯一的元素只被放入其对应的频率桶一次。
5. for(int i = bucket.length - 1; i >= 0; i--) { ... }: 从桶数组的最高频率（即 bucket.length - 1）开始，向低频率遍历。
6. if(bucket[i] != null) { ... }: 检查当前频率的桶是否为空。
7. for(int element : bucket[i]) { ... }: 遍历当前频率桶中的所有元素。由于我们是从高频率开始遍历，这些元素就是频率最高的。
8. res[counter++] = element;: 将当前元素添加到结果数组 res 中。
9. if(counter == k) { return res; }: 如果已经收集到了 K 个元素，就立即返回结果数组。

注意事项与总结

• 唯一性是核心： 在将元素放入频率桶时，务必确保每个不同的元素只被放入一次。这是为什么必须遍历 map.keySet() 而不是原始 nums 数组的原因。
• 桶数组大小： 桶数组的大小应至少为 nums.length + 1，以容纳所有可能的频率值（从 0 到 nums.length）。
• 遍历顺序： 为了找到 Top K 频繁元素，我们需要从桶数组的末尾（代表最高频率）开始向前遍历。
• 时间复杂度：
  • 统计频率：O(N)，N 是数组 nums 的长度。
  • 填充桶：O(M)，M 是 nums 中不同元素的数量，M
  • 收集结果：在最坏情况下，需要遍历所有桶和桶中的所有元素，但由于我们只收集 K 个元素，这一步的复杂度通常被 O(N) 或 O(M) 包含。
  • 总时间复杂度：O(N)。
• 空间复杂度：
  • 哈希表：O(M)，M 是不同元素的数量。
  • 桶数组：O(N)。
  • 总空间复杂度：O(N)。

通过上述方法，我们能够以线性的时间复杂度高效地解决“Top K 频繁元素”问题，并且清晰地理解了在构建频率桶时处理元素唯一性的重要性。