高效解决“前 K 个高频元素”问题:基于桶排序的Java实现与关键细节解析

梦强酱_6721

梦强酱_6721

2025-11-01

880人浏览

原创

高效解决“前 K 个高频元素”问题:基于桶排序的Java实现与关键细节解析

本文深入探讨了如何利用哈希表和桶排序高效地找出数组中出现频率最高的 k 个元素。文章详细解释了构建频率映射、利用桶排序按频率组织元素,并着重阐明了在填充频率桶时,遍历哈希表的键集(keyset)而非原始数组(nums)的重要性,以确保每个频率桶中只包含唯一的元素,从而避免结果错误。

前 K 个高频元素:基于桶排序的Java实现与关键细节解析

在数据处理和算法设计中,“找出数组中出现频率最高的 K 个元素”是一个经典问题。它常用于推荐系统、热点数据分析等场景。解决此问题有多种方法,其中一种高效且易于理解的方案是结合哈希表进行频率统计,再利用桶排序的思想组织和提取结果。

1. 问题概述与核心思路

给定一个整数数组 nums 和一个整数 k,任务是返回数组中出现频率最高的 k 个元素。返回的顺序不重要。

核心思路可以分解为以下两步:

  1. 频率统计:遍历数组,使用哈希表(HashMap)记录每个数字及其出现的频率。
  2. 频率桶排序:创建一个“桶”数组,其索引代表频率,每个桶存储具有该频率的所有数字。然后从最高频率的桶开始,依次收集元素,直到达到 k 个。

2. 频率统计:使用哈希表

第一步是计算数组中每个元素的出现频率。Java中的 HashMap 是实现这一目标的理想选择。

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字的频率
        Map<integer integer> freqMap = new HashMap();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // ... 后续步骤
    }
}</integer>

这段代码遍历 nums 数组,对于每个数字,如果它已经在 freqMap 中,则将其频率加 1;否则,将其添加到 freqMap 中,频率设为 1。

3. 构建频率桶:桶排序的巧妙应用

统计完频率后,我们需要一种方式来根据频率快速访问元素。这里引入“桶排序”的思想:

创建一个 List[] bucket 数组,其大小为 nums.length + 1。bucket 的索引 i 将代表频率 i,而 bucket[i] 中存储的是所有出现频率为 i 的数字列表。

        // ... (接上文代码)

        // 2. 创建频率桶
        // bucket[i] 存储所有频率为 i 的数字列表
        List<integer>[] 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);
        }

        // ... 后续步骤</integer>

4. 关键细节:为何必须遍历 freqMap.keySet()?

这是本解决方案中最容易混淆但至关重要的一点。许多初学者可能会疑惑,为什么不能直接遍历原始 nums 数组来填充桶,就像这样:

javascript-typescript-typescript-scaffold
javascript-typescript-typescript-scaffold

你是 TypeScript 项目架构专家,专注于脚手架搭建生产就绪的 Node.js 和前端应用。生成包含现代工具链(pnpm、Vite、Next.js)、类型

下载
        // 错误示例:遍历原始 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 <h3>6. 完整代码示例</h3><pre class="brush:php;toolbar:false;">import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字的频率
        // Key: 数字本身, Value: 该数字出现的频率
        Map<integer integer> 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<integer>[] 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 = 0 && resultIndex <h3>7. 复杂度分析</h3>
<ul>
<li>
<p><strong>时间复杂度</strong>:</p>
<ul>
<li>频率统计:遍历 nums 数组一次,O(N),其中 N 是 nums 的长度。</li>
<li>填充频率桶:遍历 freqMap.keySet() 一次,最坏情况下 O(N)(当所有元素都不同时)。</li>
<li>提取结果:遍历 bucket 数组和其中的列表,最坏情况下 O(N)(当所有元素频率都非常低,需要遍历大部分桶时)。</li>
<li>综合来看,总时间复杂度为 O(N)。</li>
</ul>
</li>
<li>
<p><strong>空间复杂度</strong>:</p>
<ul>
<li>freqMap:最坏情况下(所有元素都不同)存储 N 个<a style="color:#f60; text-decoration:underline;" title="键值对" href="https://m.php.cn/zt/49710.html" target="_blank">键值对</a>,O(N)。</li>
<li>bucket 数组:大小为 N+1,其中存储的列表总共包含 N 个元素(所有唯一的数字),O(N)。</li>
<li>综合来看,总空间复杂度为 O(N)。</li>
</ul>
</li>
</ul>
<h3>8. 总结与注意事项</h3>
<p>“前 K 个高频元素”问题通过哈希表和桶排序的组合,提供了一个高效且直观的解决方案。其中,<strong>理解并正确实现频率桶的填充过程是成功的关键</strong>。始终记住,频率桶应该存储<em>唯一的</em>数字,因此在将数字放入桶中时,必须基于哈希表的键集进行迭代,而非原始数组。这种方法在时间和空间复杂度上都达到了线性级别,使其成为解决此类问题的优秀选择。</p></integer></integer>

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
length函数用法
length函数用法

length函数用于返回指定字符串的字符数或字节数。可以用于计算字符串的长度,以便在查询和处理字符串数据时进行操作和判断。 需要注意的是length函数计算的是字符串的字符数,而不是字节数。对于多字节字符集,一个字符可能由多个字节组成。因此,length函数在计算字符串长度时会将多字节字符作为一个字符来计算。更多关于length函数的用法,大家可以阅读本专题下面的文章。

2023.09.19

2027

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7276

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

100

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

120

12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习