本文深入探讨了如何利用哈希表和桶排序高效地找出数组中出现频率最高的 k 个元素。文章详细解释了构建频率映射、利用桶排序按频率组织元素，并着重阐明了在填充频率桶时，遍历哈希表的键集（keyset）而非原始数组（nums）的重要性，以确保每个频率桶中只包含唯一的元素，从而避免结果错误。
前 K 个高频元素：基于桶排序的Java实现与关键细节解析
在数据处理和算法设计中，“找出数组中出现频率最高的 K 个元素”是一个经典问题。它常用于推荐系统、热点数据分析等场景。解决此问题有多种方法，其中一种高效且易于理解的方案是结合哈希表进行频率统计，再利用桶排序的思想组织和提取结果。
1. 问题概述与核心思路
给定一个整数数组 nums 和一个整数 k，任务是返回数组中出现频率最高的 k 个元素。返回的顺序不重要。
核心思路可以分解为以下两步：
- 频率统计：遍历数组，使用哈希表（HashMap）记录每个数字及其出现的频率。
- 频率桶排序：创建一个“桶”数组，其索引代表频率，每个桶存储具有该频率的所有数字。然后从最高频率的桶开始，依次收集元素，直到达到 k 个。
2. 频率统计：使用哈希表
第一步是计算数组中每个元素的出现频率。Java中的 HashMap 是实现这一目标的理想选择。
立即学习“Java免费学习笔记（深入）”；
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 1. 统计每个数字的频率
Map freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// ... 后续步骤
}
} 这段代码遍历 nums 数组，对于每个数字，如果它已经在 freqMap 中，则将其频率加 1；否则，将其添加到 freqMap 中，频率设为 1。
3. 构建频率桶：桶排序的巧妙应用
统计完频率后，我们需要一种方式来根据频率快速访问元素。这里引入“桶排序”的思想：
创建一个 List
// ... (接上文代码)
// 2. 创建频率桶
// bucket[i] 存储所有频率为 i 的数字列表
List[] bucket = new ArrayList[nums.length + 1];
// 遍历频率映射的键集，将数字放入对应的频率桶
for (int num : freqMap.keySet()) { // 关键点：遍历 freqMap.keySet()
int frequency = freqMap.get(num);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
bucket[frequency].add(num);
}
// ... 后续步骤 4. 关键细节：为何必须遍历 freqMap.keySet()？
这是本解决方案中最容易混淆但至关重要的一点。许多初学者可能会疑惑，为什么不能直接遍历原始 nums 数组来填充桶，就像这样：
// 错误示例：遍历原始 nums 数组填充桶
for (int num : nums) { // 错误！
int frequency = freqMap.get(num);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
bucket[frequency].add(num); // 可能会添加重复元素到桶中
}原因在于：
- 哈希表的键是唯一的：freqMap.keySet() 包含的是 nums 数组中所有不重复的数字。当我们遍历 freqMap.keySet() 时，每个数字 num 只会被考虑一次，并被放入其对应的频率桶 bucket[frequency] 中。这样，每个频率桶 bucket[i] 中存储的都是一组唯一的数字，它们都恰好出现了 i 次。
-
原始数组可能包含重复元素：如果遍历原始 nums 数组，例如 nums = [1, 1, 2, 2, 3]。
- freqMap 会是 {1: 2, 2: 2, 3: 1}。
- 当我们遍历 nums 时，第一个 1 会被放入 bucket[2]。
- 第二个 1 再次被放入 bucket[2]。此时 bucket[2] 可能包含 [1, 1]。
- 同样，2 也会被重复放入 bucket[2]。最终 bucket[2] 可能变成 [1, 1, 2, 2]。
- 结果的正确性：问题要求返回“前 K 个高频元素”，这些元素本身应该是唯一的。如果桶中存储了重复的数字，那么在后续提取结果时，我们可能会错误地将同一个数字多次计入最终结果，或者导致结果数组中出现重复。例如，如果 k=1 且 nums = [1,1,2,2]，freqMap 得到 {1:2, 2:2}。如果桶中存储了 [1,1,2,2]，那么在提取时，可能会先取到 1，再取到 1，这显然是不对的。正确的 bucket[2] 应该只包含 [1, 2]。
因此，遍历 freqMap.keySet() 是确保每个数字只被放入其频率桶一次，并且每个桶中只包含唯一数字的关键。
5. 提取前 K 个高频元素
构建完频率桶后，我们只需从最高频率的桶开始（即从 bucket 数组的末尾向前遍历），依次收集元素，直到收集到 k 个为止。
// ... (接上文代码)
// 3. 从桶中提取前 K 个高频元素
int[] result = new int[k];
int resultIndex = 0; // 用于填充结果数组的索引
// 从最高频率开始（桶数组末尾）向前遍历
for (int i = bucket.length - 1; i >= 0 && resultIndex < k; i--) {
if (bucket[i] != null) {
for (int element : bucket[i]) {
result[resultIndex++] = element;
if (resultIndex == k) { // 如果已收集到 K 个元素，则提前返回
return result;
}
}
}
}
return result; // 理论上不会执行到这里，因为 k 总是小于等于总的唯一元素数
}
}6. 完整代码示例
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 1. 统计每个数字的频率
// Key: 数字本身, Value: 该数字出现的频率
Map freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// 2. 创建频率桶
// bucket[i] 存储所有频率为 i 的数字列表
// 桶数组的大小为 nums.length + 1，因为最大频率不可能超过 nums.length
List[] bucket = new ArrayList[nums.length + 1];
// 遍历频率映射的键集 (keySet)，将每个唯一的数字放入其对应的频率桶中
// 这样做保证了每个桶中存储的数字都是唯一的
for (int num : freqMap.keySet()) {
int frequency = freqMap.get(num);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
bucket[frequency].add(num);
}
// 3. 从桶中提取前 K 个高频元素
int[] result = new int[k];
int resultIndex = 0; // 用于填充结果数组的当前索引
// 从最高频率开始（桶数组的末尾）向前遍历
// 循环条件 resultIndex < k 确保我们只收集 K 个元素
for (int i = bucket.length - 1; i >= 0 && resultIndex < k; i--) {
if (bucket[i] != null) { // 检查当前频率桶是否为空
for (int element : bucket[i]) { // 遍历当前频率桶中的所有数字
result[resultIndex++] = element; // 将数字添加到结果数组
if (resultIndex == k) { // 如果已收集到 K 个元素，则立即返回结果
return result;
}
}
}
}
return result; // 正常情况下，当 resultIndex 达到 k 时会提前返回
}
} 7. 复杂度分析
-
时间复杂度：
- 频率统计：遍历 nums 数组一次，O(N)，其中 N 是 nums 的长度。
- 填充频率桶：遍历 freqMap.keySet() 一次，最坏情况下 O(N)（当所有元素都不同时）。
- 提取结果：遍历 bucket 数组和其中的列表，最坏情况下 O(N)（当所有元素频率都非常低，需要遍历大部分桶时）。
- 综合来看，总时间复杂度为 O(N)。
-
空间复杂度：
- freqMap：最坏情况下（所有元素都不同）存储 N 个键值对，O(N)。
- bucket 数组：大小为 N+1，其中存储的列表总共包含 N 个元素（所有唯一的数字），O(N)。
- 综合来看，总空间复杂度为 O(N)。
8. 总结与注意事项
“前 K 个高频元素”问题通过哈希表和桶排序的组合，提供了一个高效且直观的解决方案。其中，理解并正确实现频率桶的填充过程是成功的关键。始终记住，频率桶应该存储唯一的数字，因此在将数字放入桶中时，必须基于哈希表的键集进行迭代，而非原始数组。这种方法在时间和空间复杂度上都达到了线性级别，使其成为解决此类问题的优秀选择。
