本文深入探讨了如何使用桶排序算法高效解决“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排版
AI排版工具，上传图文素材，秒出专业效果！
554 查看详情 
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 是有效的 }}
代码解析：
List[] bucket = new ArrayList[nums.length + 1];: 初始化一个 ArrayList 数组作为桶。数组的每个位置 i 将存储一个 ArrayList，其中包含所有频率为 i 的元素。var map = new HashMap();: 创建哈希表 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 频繁元素”问题，并且清晰地理解了在构建频率桶时处理元素唯一性的重要性。
以上就是Top K 频繁元素：桶排序算法深度解析与实现要点的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/297617.html
微信扫一扫 
支付宝扫一扫 
