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

【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 <= 105
  • k 的取值范围是 [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.题目要求&#xff1a; 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 2.解题思路&#xff1a; 代码展示&#xff1a; 1.题目要求&#xff1a; 给你一个整数数组 nums 和一个整数 k &#xff0…...

Java ---多态

&#xff08;一&#xff09;定义 官方&#xff1a;多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口&#xff0c;使用不同的实例而执行不同操作。 生活中的多态&#xff0c;如图所示&#xff1a; 多态性是对象多种表现形式的体现。 现实中&#xff0c;…...

13个程序员常用开发工具用途推荐整理

作为一名刚入门的程序员&#xff0c;选择合适的开发工具可以提高工作效率&#xff0c;加快学习进度。在本文中&#xff0c;我将向您推荐10个常用的开发工具&#xff0c;并通过简单的例子和代码来介绍它们的主要用途。 1. Visual Studio Code Visual Studio Code&#xff08;V…...

TCP分包和粘包

文章目录TCP分包和粘包TCP分包TCP 粘包分包和粘包解决方案&#xff1a;TCP分包和粘包 TCP分包 场景&#xff1a;发送方发送字符串”helloworld”&#xff0c;接收方却分别接收到了两个数据包&#xff1a;字符串”hello”和”world”发送端发送了数量较多的数据&#xff0c;接…...

手撕深度学习中的优化器

深度学习中的优化算法采用的原理是梯度下降法&#xff0c;选取适当的初值params&#xff0c;不断迭代&#xff0c;进行目标函数的极小化&#xff0c;直到收敛。由于负梯度方向时使函数值下降最快的方向&#xff0c;在迭代的每一步&#xff0c;以负梯度方向更新params的值&#…...

英文打字小游戏

目录 1 实验目的 2 实验报告内容 3 实验题目 4 实验环境 5 实验分析和设计思路 6 流程分析和类图结构 ​编辑 7. 实验结果与测试分析 8. 总结 这周没有更新任何的文章&#xff0c;感到十分的抱歉。因为我们老师让我们做一个英文打字的小游戏&#xff0c;并要求撰写实验…...

PCB生产工艺流程三:生产PCB的内层线路有哪7步

PCB生产工艺流程三&#xff1a;生产PCB的内层线路有哪7步 在我们的PCB生产工艺流程的第一步就是内层线路&#xff0c;那么它的流程又有哪些步骤呢&#xff1f;接下来我们就以内层线路的流程为主题&#xff0c;进行详细的分析。 由半固化片和铜箔压合而成&#xff0c;用于…...

算法竞赛进阶指南0x61 最短路

对于一张有向图&#xff0c;我们一般有邻接矩阵和邻接表两种存储方式。对于无向图&#xff0c;可以把无向边看作两条方向相反的有向边&#xff0c;从而采用与有向图一样的存储方式。 $$ 邻接矩阵的空间复杂度为 O(n^2)&#xff0c;因此我们一般不采用这种方式 $$ 我们用数组模…...

[学习篇] Autoreleasepool

参考文章&#xff1a; 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/ …...

晶体基本知识

文章目录晶体基本知识基本概念晶胞&#xff1c;晶格&#xff1c;晶粒&#xff1c;晶体晶胞原子坐标(原子分数坐标)六方晶系与四轴定向七大晶系和十四种点阵结构学习资料吉林大学某实验室教程---知乎系列晶体与压敏器件晶体基本知识 基本概念 晶胞&#xff1c;晶格&#xff1c…...

免费CRM如何进行选择?

如今CRM领域成为炙手可热的赛道&#xff0c;很多CRM系统厂商甚至打出完全免费的口号&#xff0c;是否真的存在完全免费的crm系统&#xff1f;很多企业在免费使用过程中会出现被迫终止的问题&#xff0c;需要花费高价钱才能继续使用&#xff0c;那么&#xff0c;免费crm系统哪个…...

关于金融类iOS套壳上架,我帮你总结了这些经验

首先说明&#xff0c;本文中出现的案例的&#xff0c;没有特别的专门针对谁&#xff0c;只是用于分析&#xff0c;如有觉得不妥的&#xff0c;请及时联系我删除&#xff0c;鉴于本文发出之后&#xff0c;可能造成的一些影响&#xff0c;所以大家看看就好了&#xff0c;千万不要…...

4年功能测试月薪9.5K,3个月时间成功进阶自动化,跳槽涨薪6k后我的路还很长...

前言 其实最开始我并不是互联网从业者&#xff0c;是经历了一场六个月的培训才入的行&#xff0c;这个经历仿佛就是一个遮羞布&#xff0c;不能让任何人知道&#xff0c;就算有面试的时候被问到你是不是被培训的&#xff0c;我还是不能承认这段历史。我是为了生存&#xff0c;…...

python url解码详解

python url解码 url是数据的一个部分&#xff0c;一般会用来做什么呢&#xff1f;比如网站的 URL&#xff0c;比如搜索引擎中的 url&#xff0c;再比如网页中的图片等。 你也许不知道&#xff0c;在 Web页面中的图片、链接、超链接都是 URL&#xff0c;也就是 url。 而如果想要…...

leetcode102:二叉树的层序遍历

给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 示例 2&#xff1a; 输入…...

深度学习openMMLab的介绍和使用

文章目录MMCV介绍MMCV的安装修改链接中的cu113修改链接中的torch1.10.0物体分类MMCLS源码下载配置参数解读配置文件的组成如何生成完整配置文件定义自己的数据集构建自己的数据集训练自己的任务物体检测MMDetection语义分割MMSegmentation姿态估计MMPose未完成&#xff0c;持续…...

【vue2】axios请求与axios拦截器的使用详解

&#x1f973;博 主&#xff1a;初映CY的前说(前端领域) &#x1f31e;个人信条&#xff1a;想要变成得到&#xff0c;中间还有做到&#xff01; &#x1f918;本文核心&#xff1a;当我们在路由跳转前与后我们可实现触发的操作 【前言】ajax是一种在javaScript代码中发请…...

文件上传都发生了啥

一直在用组件库做文件上传&#xff0c;那里面的原理到底是啥&#xff0c;自己写能不能写一个upload框出来呢? &#xff08;一&#xff09;基本原理 浏览器端提供了一个表单&#xff0c;在用户提交请求后&#xff0c;将文件数据和其他表单信息编码并上传至服务器端&#xff0…...

【vim进阶】vim编辑器的多文件操作(如何打开多个文件,如何进行文件间的切换,如何关闭其中的某一个文件)

一、如何打开多个文件&#xff1f; 方法一&#xff1a;启动打开 现在有多个文件 file1 &#xff0c;file2 , … ,filen. 现在举例打开两个文件 file1&#xff0c;file2 vim file1 file2该方式打开文件&#xff0c;显示屏默认显示第一个文件也就是 file1。 方法二&#xff…...

ToBeWritten之车辆通信

也许每个人出生的时候都以为这世界都是为他一个人而存在的&#xff0c;当他发现自己错的时候&#xff0c;他便开始长大 少走了弯路&#xff0c;也就错过了风景&#xff0c;无论如何&#xff0c;感谢经历 转移发布平台通知&#xff1a;将不再在CSDN博客发布新文章&#xff0c;敬…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...