当前位置: 首页 > news >正文

【LeetCode 热题 100】347. 前 K 个高频元素——(解法一)排序截取

Problem: 347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

文章目录

  • 整体思路
  • 完整代码
  • 时空复杂度
    • 时间复杂度:O(N + M log M)
    • 空间复杂度:O(M)

整体思路

这段代码同样旨在解决 “前 K 个高频元素” 问题。此版本的实现策略非常直接,可以概括为 “先统计,后排序,再截取”,充分利用了Java的集合框架和Collections工具类。

算法的整体思路可以清晰地分解为以下三个步骤:

  1. 第一步:频率统计

    • 算法首先使用一个 哈希表 (HashMap) frequencyMap 来高效地统计数组 nums 中每个数字出现的频率。
    • 遍历结束后,frequencyMap 中存储了 {数字 -> 出现次数} 的完整映射关系。
  2. 第二步:转换为列表并排序

    • 由于 HashMap 本身是无序的,无法直接按值排序。因此,算法需要将 map 中的数据转换到一个可以排序的结构中。
    • 转换:通过 new ArrayList<>(frequencyMap.entrySet()),将 map 的键值对集合(entrySet)转换成一个 ArrayList。列表中的每个元素都是一个 Map.Entry<Integer, Integer> 对象。
    • 排序:调用 Collections.sort() 对这个 entryList 进行排序。这是算法的核心操作。
      • 它使用了一个自定义的比较器(通过lambda表达式 (a, b) -> (b.getValue() - a.getValue()) 提供),该比较器指示 sort 方法应该根据 Map.Entry 的值(getValue(),即频率)来进行比较。
      • b.getValue() - a.getValue() 的结果决定了排序顺序。当 b 的频率大于 a 时,结果为正,b 会被排在 a 的前面,从而实现了按频率降序排序。
  3. 第三步:提取结果

    • 经过排序后,entryList 的前 k 个元素就是频率最高的 k 个键值对。
    • 算法创建一个大小为 k 的结果数组 ans,然后通过一个简单的 for 循环,遍历排序后列表的前 k 项,提取出每个 Entry 的键(getKey(),即原始数字),并存入 ans 数组。
    • 最后返回 ans 数组。

这个方法逻辑清晰,代码可读性好,但由于对所有唯一元素进行了完全排序,其性能在 k 远小于唯一元素数量 M 时,不如使用最小堆的 O(N log k) 方法。

完整代码

class Solution {/*** 找出数组中出现频率最高的前 k 个元素。* @param nums 整数数组* @param k 需要找出的元素个数* @return 包含前 k 个高频元素的数组*/public int[] topKFrequent(int[] nums, int k) {// 步骤 1: 使用 HashMap 统计每个数字的出现频率Map<Integer, Integer> frequencyMap = new HashMap<>();for (int num : nums) {frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);}// 步骤 2: 将 Map 的条目转换为列表,以便进行排序List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(frequencyMap.entrySet());// 使用 Collections.sort 和自定义比较器,按频率(entry 的 value)进行降序排序// (a, b) -> (b.getValue() - a.getValue()) 实现了降序排列Collections.sort(entryList, (a, b) -> (b.getValue() - a.getValue()));// 步骤 3: 提取排序后列表的前 k 个元素的键(即原始数字)int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = entryList.get(i).getKey();}    return ans;}
}

时空复杂度

时间复杂度:O(N + M log M)

  1. 频率统计:遍历 nums 数组一次,填充哈希表。时间复杂度为 O(N),其中 Nnums 的长度。
  2. Map 转 List:将哈希表中的 M 个唯一元素的条目复制到列表中。时间复杂度为 O(M),其中 M 是唯一元素的数量。
  3. 排序 (Collections.sort):这是时间开销最大的部分。对包含 M 个条目的列表进行排序,其时间复杂度为 O(M log M)
  4. 提取结果:遍历排序后列表的前 k 个元素,时间复杂度为 O(k)

综合分析
总时间复杂度 = O(N) + O(M) + O(M log M) + O(k)。
由于 k <= M <= N,其中 O(M log M) 是主导项(除非 N 异常巨大而 M 极小)。
因此,最终的时间复杂度可以写为 O(N + M log M)

空间复杂度:O(M)

  1. 主要存储开销
    • HashMap frequencyMap: 需要存储所有 M 个唯一元素及其频率。空间为 O(M)
    • List<Map.Entry> entryList: 需要存储这 M 个键值对。空间为 O(M)
    • 排序的内部空间Collections.sort(在后台使用 Timsort)对列表排序时,会需要一些额外的空间,最坏情况下为 O(M)。

综合分析
算法所需的额外空间主要由哈希表和列表决定。因此,总的空间复杂度为 O(M),其中 M 是数组中唯一元素的数量。

http://www.lryc.cn/news/610740.html

相关文章:

  • Redis类型之String
  • 【npm 解决】---- TypeError: crypto.hash is not a function
  • GPS信号捕获尝试
  • 【机器学习深度学习】模型剪枝
  • Python包安全工程实践:构建安全可靠的Python生态系统
  • 【学习笔记】NTP时间同步验证
  • 期权定价全解析:从Black-Scholes到量子革命的金融基石
  • Linux 逻辑卷管理:LVM 原理与 Stratis、VDO 特性对比
  • 基于 Spring Boot 的小区人脸识别与出入记录管理系统实现
  • 力扣经典算法篇-43-全排列(经典回溯问题)
  • css3属性总结和浏览器私有属性
  • Python、Java、C#实现浮点型转换为转型
  • Mysql使用Canal服务同步数据->ElasticSearch
  • 电子秤利用Websocket做为Client向MES系统推送数据
  • 文件编译、调试及库制作
  • 跑yolov5的train.py时,ImportError: Failed to initialize: Bad git executable.
  • 前端实现Excel文件的在线预览效果
  • 【机器学习】算法调参的两种方式:网格搜索(枚举)、随机搜索
  • 【力扣 Hot100】 刷题日记
  • Python分块读取大型Excel文件
  • 豆包新模型与 PromptPilot 实操体验测评,AI 辅助创作的新范式探索
  • LangGraph学习笔记 — LangGraph中State状态模式
  • 自动驾驶控制算法——MPC控制算法
  • qq scheme
  • GaussDB 并行创建索引
  • 使用iptables的nat链表进行端口转发
  • 基于MATLAB实现的频域模态参数识别方法
  • 算法3. 无重复字符的最长子串
  • Django中的转发与重定向详解
  • Boosting 知识点整理:机制、对比与应用场景