本文深入探讨了如何使用桶排序算法高效解决“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<Integer, Integer>();
for(int n : nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}这段代码遍历 nums 数组，对于每个元素 n，如果它已存在于 map 中，则将其频率加 1；否则，将其添加到 map 中，并将频率初始化为 1。
第二步：构建频率桶
在统计完所有元素的频率后，我们可以创建一个“桶”数组。这个桶数组是一个 List<Integer>[] 类型，其中数组的索引代表元素的频率，而该索引处存储的 List 则包含所有具有该频率的元素。例如，bucket[3] 将是一个列表，其中包含所有出现了 3 次的元素。桶数组的大小通常为 nums.length + 1，因为元素的最高频率不会超过数组的长度。
List<Integer>[] bucket = new ArrayList[nums.length + 1];
关键抉择：遍历 keySet() 与遍历原始数组 nums 的区别
在将元素放入频率桶时，一个常见的疑问是：应该遍历哈希表的键集（map.keySet()）还是原始数组（nums）？这正是本问题中的核心困惑点。
为什么选择 map.keySet()
正确的做法是遍历 map.keySet()。map.keySet() 返回的是哈希表中所有唯一键的集合。这意味着我们只会处理每个不同的元素一次。
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
for(int n : map.keySet()) {
int freq = map.get(n); // 获取元素 n 的频率
if(bucket[freq] == null) {
bucket[freq] = new ArrayList<Integer>();
}
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<Integer>();
}
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<Integer>[] bucket = new ArrayList[nums.length + 1];
// 2. 使用 HashMap 统计每个元素的频率。
var map = new HashMap<Integer, Integer>();
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<Integer>();
}
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 是有效的
}
}代码解析：
- List<Integer>[] bucket = new ArrayList[nums.length + 1];: 初始化一个 ArrayList 数组作为桶。数组的每个位置 i 将存储一个 ArrayList，其中包含所有频率为 i 的元素。
- var map = new HashMap<Integer, Integer>();: 创建哈希表 map，用于存储 元素 -> 频率 的映射。
- for(int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);: 遍历输入数组 nums，计算每个元素的频率并存储在 map 中。
- for(int n : map.keySet()) { ... }: 这是关键步骤。 遍历 map 的键集，即所有不同的元素。对于每个元素 n，获取其频率 freq，然后将其添加到 bucket[freq] 对应的列表中。这一步确保了每个唯一的元素只被放入其对应的频率桶一次。
- for(int i = bucket.length - 1; i >= 0; i--) { ... }: 从桶数组的最高频率（即 bucket.length - 1）开始，向低频率遍历。
- if(bucket[i] != null) { ... }: 检查当前频率的桶是否为空。
- for(int element : bucket[i]) { ... }: 遍历当前频率桶中的所有元素。由于我们是从高频率开始遍历，这些元素就是频率最高的。
- res[counter++] = element;: 将当前元素添加到结果数组 res 中。
- 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 <= N。
- 收集结果：在最坏情况下，需要遍历所有桶和桶中的所有元素，但由于我们只收集 K 个元素，这一步的复杂度通常被 O(N) 或 O(M) 包含。
- 总时间复杂度：O(N)。
-
空间复杂度：
- 哈希表：O(M)，M 是不同元素的数量。
- 桶数组：O(N)。
- 总空间复杂度：O(N)。
通过上述方法，我们能够以线性的时间复杂度高效地解决“Top K 频繁元素”问题，并且清晰地理解了在构建频率桶时处理元素唯一性的重要性。
