本文深入探讨了“top k 频繁元素”问题的高效解决方案，主要采用哈希映射统计元素频率，并结合桶排序思想进行元素归类。文章详细解析了如何构建频率桶，并重点澄清了在填充桶时，为何必须遍历哈希映射的键集（keyset）而非原始数组，以避免将重复元素错误地放入桶中，确保最终输出的正确性。
问题概述
“Top K 频繁元素”问题要求从一个整数数组中找出出现频率最高的 K 个元素。例如，给定数组 nums = [1,1,1,2,2,3] 和 k = 2，预期输出为 [1,2]，因为 1 出现了 3 次，2 出现了 2 次，它们是频率最高的两个元素。解决此问题通常需要两个核心步骤：首先统计每个元素的频率，然后根据频率筛选出前 K 个元素。
核心思想：频率统计与桶排序
解决此类问题的常见且高效的方法是结合使用哈希映射（HashMap）进行频率统计，以及桶排序（Bucket Sort）思想进行元素归类。
-
频率统计：遍历输入数组 nums，使用 HashMap
存储每个元素及其出现的频率。键为数组中的元素，值为其出现次数。 - 桶排序：创建一个列表数组（或称“桶”），其索引代表元素的频率，而该索引处存储的列表则包含所有具有该频率的元素。例如，bucket[3] 将存储所有出现频率为 3 的元素。由于频率最大不会超过数组长度，因此桶数组的大小通常为 nums.length + 1。
完成这两个步骤后，只需从桶数组的末尾（即高频率）向前遍历，收集元素直到达到 K 个，即可得到结果。
Java实现详解
以下是基于上述思想的 Java 解决方案代码：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 1. 统计每个元素的频率
Map freqMap = new HashMap<>();
for (int n : nums) {
freqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
}
// 2. 创建频率桶
// 桶的索引代表频率，桶内存储具有该频率的元素列表
// 频率最大为 nums.length，所以桶大小为 nums.length + 1
List[] bucket = new ArrayList[nums.length + 1];
// 3. 将元素放入对应的频率桶中
// 遍历 freqMap 的 keySet，确保每个不重复的元素被放入桶中一次
for (int n : freqMap.keySet()) {
int freq = freqMap.get(n);
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(n);
}
// 4. 从高频率向低频率遍历桶，收集前 K 个元素
int[] result = new int[k];
int count = 0; // 已收集的元素数量
// 从桶的末尾（最高频率）开始遍历
for (int i = bucket.length - 1; i >= 0; i--) {
if (bucket[i] != null) { // 如果当前频率的桶不为空
for (int element : bucket[i]) {
result[count++] = element;
if (count == k) { // 达到 K 个元素，返回结果
return result;
}
}
}
}
return result; // 理论上不会执行到这里，除非 k > 数组中所有不重复元素的数量
}
} 关键细节：为何遍历 map.keySet() 而非 nums 数组
在上述解决方案中，将元素放入频率桶的关键步骤是：
for (int n : freqMap.keySet()) { // 注意这里是 freqMap.keySet()
int freq = freqMap.get(n);
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(n);
}有些开发者可能会疑惑，为什么不能直接遍历原始 nums 数组来填充桶，例如：
// 错误的示例：遍历 nums 数组来填充桶
for (int n : nums) { // 这里是 nums 数组
int freq = freqMap.get(n); // 获取元素 n 的频率
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(n); // 将元素 n 添加到对应频率的桶中
}原因分析：
哈希映射 freqMap 的键是唯一的，它存储了数组中所有不重复的元素。当我们遍历 freqMap.keySet() 时，我们实际上是在遍历数组中所有不同的元素。对于每个不同的元素 n，我们获取其在 freqMap 中统计出的总频率 freq，然后将这个唯一的元素 n 添加到 bucket[freq] 列表中。这意味着 bucket[freq] 列表最终会包含所有频率为 freq 的不同元素。
然而，如果选择遍历原始 nums 数组，情况就不同了。nums 数组可能包含重复元素。例如，nums = [1, 1, 1, 2, 2, 3]。 当 n = 1 第一次出现时，它会被添加到 bucket[3] 中。 当 n = 1 第二次出现时，它又会被添加到 bucket[3] 中。 当 n = 1 第三次出现时，它还会被添加到 bucket[3] 中。 最终，bucket[3] 可能会变成 [1, 1, 1]。
这会导致以下问题：
- 数据冗余：bucket[freq] 列表中包含了重复的元素，违背了桶的初衷（每个桶应该存储具有相同频率的不同元素）。
- 结果错误：在最后遍历桶收集结果时，如果 bucket[i] 包含 [1, 1, 1]，那么 for (int element : bucket[i]) 循环会将 1 添加到结果数组三次，这显然是错误的。Top K 频繁元素要求返回的是元素本身，而不是其出现的次数的列表。我们只需要 1 这个元素一次。
因此，为了确保 bucket[freq] 列表中只包含唯一的、具有特定频率的元素，必须遍历 freqMap.keySet()。
复杂度分析
-
时间复杂度：
- 频率统计：遍历 nums 数组一次，时间复杂度为 O(N)，其中 N 是数组长度。
- 填充桶：遍历 freqMap.keySet() 一次，哈希映射中最多有 N 个不重复元素，时间复杂度为 O(N)。
- 收集结果：最坏情况下需要遍历整个 bucket 数组和其中的所有元素，时间复杂度为 O(N)。
- 总时间复杂度：O(N)。
-
空间复杂度：
- freqMap：最坏情况下存储 N 个不重复元素，空间复杂度为 O(N)。
- bucket：数组大小为 N+1，最坏情况下所有元素都存储在桶中，空间复杂度为 O(N)。
- 总空间复杂度：O(N)。
注意事项与总结
- 桶数组大小：new ArrayList[nums.length + 1] 的设计是关键，因为它确保了所有可能的频率（从 0 到 nums.length）都有对应的存储位置。
- 空桶处理：在遍历桶收集结果时，需要检查 if (bucket[i] != null)，因为并非所有频率都会有对应的元素。
- K值的处理：当收集到的元素数量达到 k 时，应立即返回结果，避免不必要的遍历。
- 其他解决方案：除了桶排序，该问题也可以使用最小堆（Min-Heap）来解决。先用哈希映射统计频率，然后将频率和元素对放入大小为 K 的最小堆中。当堆满时，如果新元素的频率大于堆顶元素的频率，则弹出堆顶元素并插入新元素。这种方法的时间复杂度通常为 O(N log K)。对于 K 值较小的情况，堆的性能可能更优；对于 K 值较大或接近 N 的情况，桶排序的 O(N) 复杂度通常更具优势。
通过本文的详细解析，我们不仅掌握了“Top K 频繁元素”问题的桶排序解决方案，更重要的是理解了在构建频率桶时遍历 map.keySet() 的必要性，从而避免了常见的逻辑陷阱。
