【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博客发布新文章,敬…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
