当前位置: 首页 > 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;敬…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...