【LeetCode】前 K 个高频元素(堆)
目录
1.题目要求:
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
2.解题思路:
代码展示:
1.题目要求:
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示:
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一,换句话说,数组中前
k个高频元素的集合是唯一的
2.解题思路:
创建一个哈希表,用其存放数组中出现的元素以及每个元素出现的次数
//用哈希表存储出现的元素,和出现的次数Map<Integer,Integer> map = new HashMap<>();for (int i:nums) {if(map.containsKey(i)){map.put(i,map.get(i) + 1);}else {map.put(i,1);}}
先创建一个类numOfTimes , 其中有两个属性,一个key值,一个k值出现的次数
//创建一个类,其中两个属性,一个k值,一个k值出现的次数
class numOfTimes{int key;int times;public numOfTimes(int key, int times) {this.key = key;this.times = times;}
}
写一个类numsSortWayOfTimes继承Comparator方法接口,重写compare方法(对numOfTimes对象进行排序比较的方式---key值出现的次数times的大小)
class numsSortWayOfTimes implements Comparator<numOfTimes> {@Overridepublic int compare(numOfTimes o1, numOfTimes o2) {return o1.times - o2.times;}
}
将map内的key值按照出现次数进行比大小
建立一个优先级队列大小为k,存储(元素与出现次数的)numOfTimes的对象
遍历队列后就会将出现次数最多的元素对象留在了堆中
//将map内的key值按照出现次数进行比大小//建立一个优先级队列大小为k,存储(元素与出现次数的)numOfTimes的对象//遍历队列后就会将出现次数最多的元素留在了堆中Queue<numOfTimes> queue = new PriorityQueue<>(new numsSortWayOfTimes());//遍历map,将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.Entry<Integer,Integer> entry:map.entrySet()) {queue.offer(new numOfTimes(entry.getKey(),entry.getValue()));if(queue.size() > k){queue.poll();}}
此时队列中存放的就是出现次数最多的元素对象
遍历队列将对象的key值保存在数组中,返回该数组即可
//此时队列中存放的就是出现次数最多的元素//遍历队列将key值保存在数组中int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = queue.poll().key;}return res;
代码展示:
import java.util.*;//创建一个类,其中两个属性,一个k值,一个k值出现的次数
class numOfTimes{int key;int times;public numOfTimes(int key, int times) {this.key = key;this.times = times;}
}//对numOfTimes进行排序比较的方式,(出现次数)
//继承Comparator接口重写compare方法
class numsSortWayOfTimes implements Comparator<numOfTimes> {@Overridepublic int compare(numOfTimes o1, numOfTimes o2) {return o1.times - o2.times;}
}public class Leetcode_347 {//给你一个整数数组 nums 和一个整数 k ,// 请你返回其中出现频率前 k 高的元素。// 你可以按 任意顺序 返回答案。
// 输入: nums = [1,1,1,2,2,3], k = 2
// 输出: [1,2]public int[] topKFrequent(int[] nums, int k) {//用哈希表存储出现的元素,和出现的次数Map<Integer,Integer> map = new HashMap<>();for (int i:nums) {if(map.containsKey(i)){map.put(i,map.get(i) + 1);}else {map.put(i,1);}}//将map内的key值按照出现次数进行比大小//建立一个优先级队列大小为k,存储(元素与出现次数的)numOfTimes的对象//遍历队列后就会将出现次数最多的元素留在了堆中Queue<numOfTimes> queue = new PriorityQueue<>(new numsSortWayOfTimes());//遍历map,将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.Entry<Integer,Integer> entry:map.entrySet()) {queue.offer(new numOfTimes(entry.getKey(),entry.getValue()));if(queue.size() > k){queue.poll();}}//此时队列中存放的就是出现次数最多的元素//遍历队列将key值保存在数组中int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = queue.poll().key;}return res;}
}
相关文章:
【LeetCode】前 K 个高频元素(堆)
目录 1.题目要求: 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 2.解题思路: 代码展示: 1.题目要求: 给你一个整数数组 nums 和一个整数 k ࿰…...
Java ---多态
(一)定义 官方:多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口,使用不同的实例而执行不同操作。 生活中的多态,如图所示: 多态性是对象多种表现形式的体现。 现实中,…...
13个程序员常用开发工具用途推荐整理
作为一名刚入门的程序员,选择合适的开发工具可以提高工作效率,加快学习进度。在本文中,我将向您推荐10个常用的开发工具,并通过简单的例子和代码来介绍它们的主要用途。 1. Visual Studio Code Visual Studio Code(V…...
TCP分包和粘包
文章目录TCP分包和粘包TCP分包TCP 粘包分包和粘包解决方案:TCP分包和粘包 TCP分包 场景:发送方发送字符串”helloworld”,接收方却分别接收到了两个数据包:字符串”hello”和”world”发送端发送了数量较多的数据,接…...
手撕深度学习中的优化器
深度学习中的优化算法采用的原理是梯度下降法,选取适当的初值params,不断迭代,进行目标函数的极小化,直到收敛。由于负梯度方向时使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新params的值&#…...
英文打字小游戏
目录 1 实验目的 2 实验报告内容 3 实验题目 4 实验环境 5 实验分析和设计思路 6 流程分析和类图结构 编辑 7. 实验结果与测试分析 8. 总结 这周没有更新任何的文章,感到十分的抱歉。因为我们老师让我们做一个英文打字的小游戏,并要求撰写实验…...
PCB生产工艺流程三:生产PCB的内层线路有哪7步
PCB生产工艺流程三:生产PCB的内层线路有哪7步 在我们的PCB生产工艺流程的第一步就是内层线路,那么它的流程又有哪些步骤呢?接下来我们就以内层线路的流程为主题,进行详细的分析。 由半固化片和铜箔压合而成,用于…...
算法竞赛进阶指南0x61 最短路
对于一张有向图,我们一般有邻接矩阵和邻接表两种存储方式。对于无向图,可以把无向边看作两条方向相反的有向边,从而采用与有向图一样的存储方式。 $$ 邻接矩阵的空间复杂度为 O(n^2),因此我们一般不采用这种方式 $$ 我们用数组模…...
[学习篇] Autoreleasepool
参考文章: https://www.jianshu.com/p/ec2c854b2efd https://suhou.github.io/2018/01/21/%E5%B8%A6%E7%9D%80%E9%97%AE%E9%A2%98%E7%9C%8B%E6%BA%90%E7%A0%81----%E5%AD%90%E7%BA%BF%E7%A8%8BAutoRelease%E5%AF%B9%E8%B1%A1%E4%BD%95%E6%97%B6%E9%87%8A%E6%94%BE/ …...
晶体基本知识
文章目录晶体基本知识基本概念晶胞<晶格<晶粒<晶体晶胞原子坐标(原子分数坐标)六方晶系与四轴定向七大晶系和十四种点阵结构学习资料吉林大学某实验室教程---知乎系列晶体与压敏器件晶体基本知识 基本概念 晶胞<晶格<…...
免费CRM如何进行选择?
如今CRM领域成为炙手可热的赛道,很多CRM系统厂商甚至打出完全免费的口号,是否真的存在完全免费的crm系统?很多企业在免费使用过程中会出现被迫终止的问题,需要花费高价钱才能继续使用,那么,免费crm系统哪个…...
关于金融类iOS套壳上架,我帮你总结了这些经验
首先说明,本文中出现的案例的,没有特别的专门针对谁,只是用于分析,如有觉得不妥的,请及时联系我删除,鉴于本文发出之后,可能造成的一些影响,所以大家看看就好了,千万不要…...
4年功能测试月薪9.5K,3个月时间成功进阶自动化,跳槽涨薪6k后我的路还很长...
前言 其实最开始我并不是互联网从业者,是经历了一场六个月的培训才入的行,这个经历仿佛就是一个遮羞布,不能让任何人知道,就算有面试的时候被问到你是不是被培训的,我还是不能承认这段历史。我是为了生存,…...
python url解码详解
python url解码 url是数据的一个部分,一般会用来做什么呢?比如网站的 URL,比如搜索引擎中的 url,再比如网页中的图片等。 你也许不知道,在 Web页面中的图片、链接、超链接都是 URL,也就是 url。 而如果想要…...
leetcode102:二叉树的层序遍历
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入…...
深度学习openMMLab的介绍和使用
文章目录MMCV介绍MMCV的安装修改链接中的cu113修改链接中的torch1.10.0物体分类MMCLS源码下载配置参数解读配置文件的组成如何生成完整配置文件定义自己的数据集构建自己的数据集训练自己的任务物体检测MMDetection语义分割MMSegmentation姿态估计MMPose未完成,持续…...
【vue2】axios请求与axios拦截器的使用详解
🥳博 主:初映CY的前说(前端领域) 🌞个人信条:想要变成得到,中间还有做到! 🤘本文核心:当我们在路由跳转前与后我们可实现触发的操作 【前言】ajax是一种在javaScript代码中发请…...
文件上传都发生了啥
一直在用组件库做文件上传,那里面的原理到底是啥,自己写能不能写一个upload框出来呢? (一)基本原理 浏览器端提供了一个表单,在用户提交请求后,将文件数据和其他表单信息编码并上传至服务器端࿰…...
【vim进阶】vim编辑器的多文件操作(如何打开多个文件,如何进行文件间的切换,如何关闭其中的某一个文件)
一、如何打开多个文件? 方法一:启动打开 现在有多个文件 file1 ,file2 , … ,filen. 现在举例打开两个文件 file1,file2 vim file1 file2该方式打开文件,显示屏默认显示第一个文件也就是 file1。 方法二ÿ…...
ToBeWritten之车辆通信
也许每个人出生的时候都以为这世界都是为他一个人而存在的,当他发现自己错的时候,他便开始长大 少走了弯路,也就错过了风景,无论如何,感谢经历 转移发布平台通知:将不再在CSDN博客发布新文章,敬…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
