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

Leetcode 前 k 个高频元素

在这里插入图片描述

使用最小堆算法来解决这道题目:相当于有一个容量固定为K的教室,只能容纳 K 个人,学生们逐个逐个进入该教室,当教室容量达到K人之后,每次进入一个新的学生后,我们将分数最低的学生(类似本题中的频率最低元素)赶出去,最后所有学生都遍历结束之后,教室里所余的学生就是成绩前K高的学生们。

在这道题目中,最小堆(PriorityQueue)就像是一个只能容纳 K 个学生的教室,每次加入一个新的学生,教室满了就会将成绩最低的学生(即频率最低的元素)移除出去。最终剩下的 K 个学生,就是成绩最高的 K 个学生。

具体步骤如下:

  1. 我们先统计每个元素的出现频率(类似学生的分数)。
  2. 然后我们使用一个容量为 K 的最小堆来维护当前频率最高的 K 个元素。
    • 当堆的大小超过K时,将频率最低的元素移除,这样堆中始终只会保留频率最高的K个元素。
  3. 最后,堆中剩下的元素就是前K个高频元素。

这个方法的复杂度主要取决于建立和维护堆的过程,大概是O(N log K) 的时间复杂度,其中N是数组的长度,K是要返回的高频元素的个数。

class Solution {public int[] topKFrequent(int[] nums, int k) {//首先利用 Hashmap 统计每个数值的频率Map<Integer, Integer> freqMap = new HashMap<>();for(int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);}//创建最小堆,存储键值对对象,key 代表元素,value 代表对应的频率值. // 比较器 (a, b) -> a.getValue() - b.getValue() 隐式地比较了两个元素的频率 // 如果 a 的值(频率)小于 b,则 a 会排在 b 前面(因为最小堆会将频率最小的元素放在堆顶)PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, (a, b) -> a.getValue() - b.getValue());    //维护一个大小为 k 的最小堆for(Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {// 遍历插入一个新的键值对,而不是元素;键是唯一的,没有重复//由于堆顶元素始终是最小的元素,所以无论当前offer提供的待插入元素的大小与此时堆顶元素的大小如何,都会被插入堆中并自动调整。minHeap.offer(entry);if(minHeap.size() > k) { minHeap.poll(); }}int[] results = new int[k];for(int i = 0; i < k; ++i) {results[i] = minHeap.poll().getKey();}return results;}
}

相关文章:

Leetcode 前 k 个高频元素

使用最小堆算法来解决这道题目&#xff1a;相当于有一个容量固定为K的教室&#xff0c;只能容纳 K 个人&#xff0c;学生们逐个逐个进入该教室&#xff0c;当教室容量达到K人之后&#xff0c;每次进入一个新的学生后&#xff0c;我们将分数最低的学生(类似本题中的频率最低元素…...

[LeetCode] 面试题01.02 判定是否互为字符重拍

题目描述&#xff1a; 给定两个由小写字母组成的字符串 s1 和 s2&#xff0c;请编写一个程序&#xff0c;确定其中一个字符串的字符重新排列后&#xff0c;能否变成另一个字符串。 示例 1&#xff1a; 输入: s1 "abc", s2 "bca" 输出: true 示例 2&am…...

数据结构-4.5.KMP算法(旧版上)-朴素模式匹配算法的优化

朴素模式匹配算法最坏的情况&#xff1a; 一.实例&#xff1a; 第一轮匹配失败&#xff0c;开始下一轮的匹配&#xff1a; 不断的操作&#xff0c;最终匹配成功&#xff1a; 如上述图片所述&#xff0c;朴素模式匹配算法会导致时间开销增加&#xff0c; 优化思路&#xff1a;主…...

STM32 QSPI接口驱动GD/W25Qxx配置简要

STM32 QSPI接口GD/W25Qxx配置简要 &#x1f4dd;本篇会具体涉及介绍Winbond&#xff08;华邦&#xff09;和GD(兆易创新) NOR flash相关型号指令差异。由于网络上可以搜索到很多相关QSPI相关知识内容&#xff0c;不对QSPI通讯协议做深度解析。 &#x1f516;首先确保所使用的ST…...

UCI-HAR数据集深度剖析:训练仿真与可视化解读

在本篇文章中&#xff0c;我们将深入探讨如何使用Python对UCI人类活动识别&#xff08;HAR&#xff09;数据集进行分割和预处理&#xff0c;以及运用模型网络CNN对数据集进行训练仿真和可视化解读。 一、UCI-HAR数据集分析及介绍 UCI-HAR数据集是一个公开的数据集&#xff0c…...

牛客SQL练习详解 06:综合练习

牛客SQL练习详解 06&#xff1a;综合练习 SQL34 统计复旦用户8月练题情况SQL35 浙大不同难度题目的正确率SQL39 21年8月份练题总数 叮嘟&#xff01;这里是小啊呜的学习课程资料整理。好记性不如烂笔头&#xff0c;今天也是努力进步的一天。一起加油进阶吧&#xff01; SQL34 统…...

k8s apiserver高可用方案

目前官方推荐有 2 种方式部署k8s apiserver 高可用 keepalived and haproxy 部署有2种方式&#xff0c;一种是systemd管理的&#xff0c;另一种是pod形式&#xff0c;使用那种可以根据实际情况选择 服务部署 systemd方式 可以通过包管理工具安装&#xff0c;正常启动之后&…...

服务器数据恢复—硬盘坏扇区导致Linux系统服务器数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 一台linux操作系统网站服务器&#xff0c;该服务器上部署了几十个网站&#xff0c;使用一块SATA硬盘。 服务器故障&原因&#xff1a; 服务器在工作过程中突然宕机。管理员尝试重新启动服务器失败&#xff0c;于是将服务器上的硬盘拆下检测…...

【多线程】多线程(12):多线程环境下使用哈希表

【多线程环境下使用哈希表&#xff08;重点掌握&#xff09;】 可以使用类&#xff1a;“ConcurrentHashMap” ★ConcurrentHashMap对比HashMap和Hashtable的优化点 1.优化了锁的粒度【最核心】 //Hashtable的加锁&#xff0c;就是直接给put&#xff0c;get等方法加上synch…...

轻量服务器和云服务器ecs哪个好用一些?

轻量服务器和云服务器ecs哪个好用一些&#xff1f;轻量服务器与云服务器ECS在多方面存在显著差异&#xff0c;对于需要高性能计算和大规模数据处理的用户来说&#xff0c;ECS可能是更好的选择&#xff1b;而对于预算有限且需求较为简单的用户来说&#xff0c;轻量服务器可能更为…...

【交通标志识别系统】Python+卷积神经网络算法+人工智能+深度学习+机器学习+算法模型

一、介绍 交通标志识别系统。本系统使用Python作为主要编程语言&#xff0c;在交通标志图像识别功能实现中&#xff0c;基于TensorFlow搭建卷积神经网络算法模型&#xff0c;通过对收集到的58种常见的交通标志图像作为数据集&#xff0c;进行迭代训练最后得到一个识别精度较高…...

特种设备作业叉车司机试题附答案

1.发生事故要本着"&#xff08; &#xff09;不放过"的原则,查明原因、分清责任、严肃处理。 A.三 B.四 C.五 答案:B 2.柴油发动机在压缩行程终了时气体的温度和压力都比汽油机&#xff08; &#xff09;。 A.低 B.高 C.相同 答案:B 3.柴油发动机的压缩比比汽…...

【Nginx系列】Nginx启动失败

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

2024/10/12 计组大题专训

2018&#xff1a; 2019&#xff1a; 2020&#xff1a; 2021&#xff1a;...

2024年腾讯外包面试题(微创公司)

笔试&#xff1a; 1、判断异步执行顺序 console.log(1);setTimeout(()>{Promise.resolve().then(()>{console.log(2);})console.log(3);},0);new Promise ((resolve)>{for(let i0; i<1000;i ){if(i1000){resolve();}}console.log(4);}).then(()>{console.log(5…...

nginx运行时报:No rule to make target ‘build‘, needed by ‘deault‘.Stop

项目场景&#xff1a; 部署前端项目&#xff0c;将打好的前端包&#xff0c;放到服务器上&#xff0c;运行nginx执行&#xff0c;结果nginx运行报错。 问题描述 nginx运行报以下错误&#xff1a; No rule to make target ‘build‘, needed by ‘deault‘.Stop原因分析&…...

dvwa:暴力破解、命令注入、csrf全难度详解

暴力破解 easy模式 hydra -L /usr/share/wordlists/SecLists-master/Usernames/top-usernames-shortlist.txt -P /usr/share/wordlists/SecLists-master/Passwords/500-worst-passwords.txt 192.168.72.1 http-get-form "/dvwa/vulnerabilities/brute/:username^USER^&…...

Java-学生管理系统[初阶]

这次我们来尝试使用Java实现一下"学生管理系统"&#xff0c;顾名思义&#xff0c;就是实现一个能用来管理学生各种数据的系统。在后续学习中我们将对"学生管理系统"进行两种实现&#xff1a; &#x1f4da; 学生管理系统[初阶](不带模拟登录系统) &#…...

微信小程序 详情图片预览功能实现详解

详情图片预览功能实现详解 在开发微信小程序时&#xff0c;我们经常需要实现点击商品图片进行全屏预览的功能。这不仅提升了用户体验&#xff0c;还允许用户进行保存图片、发送给朋友等操作。本文将详细介绍如何实现这一功能。 思路分析 当用户在商品详情页点击图片时&#…...

LeetCode 48 Rotate Image 解题思路和python代码

题目&#xff1a; You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and …...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...