2024.1.23(347.前k个高频元素)
2024.1.23(347.前k个高频元素)

思路
这道题目主要涉及到如下三块内容:
1.要统计元素出现频率
2.对频率排序
3.找出前K个高频元素
首先统计元素出现的频率,这一类的问题可以使用map来进行统计。
然后是对频率进行排序,这里我们可以使用一种 容器适配器就是优先级队列。
什么是优先级队列呢?
其实就是一个披着队列外衣的堆,因为优先级队列对外接口只是从队头取元素,从队尾添加元素,再无其他取元素的方式,看起来就是一个队列。
而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢?
缺省情况下priority_queue利用max-heap(大顶堆)完成对元素的排序,这个大顶堆是以vector为表现形式的complete binary tree(完全二叉树)。
什么是堆呢?
堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆(堆头是最大元素),小顶堆(堆头是最小元素),如果懒得自己实现的话,就直接用priority_queue(优先级队列)就可以了,底层实现都是一样的,从小到大排就是小顶堆,从大到小排就是大顶堆。
本题我们就要使用优先级队列来对部分频率进行排序。
为什么不用快排呢, 使用快排要将map转换为vector的结构,然后对整个数组进行排序, 而这种场景下,我们其实只需要维护k个有序的序列就可以了,所以使用优先级队列是最优的。
此时要思考一下,是使用小顶堆呢,还是大顶堆?
有的同学一想,题目要求前 K 个高频元素,那么果断用大顶堆啊。
那么问题来了,定义一个大小为k的大顶堆,在每次移动更新大顶堆的时候,每次弹出都把最大的元素弹出去了,那么怎么保留下来前K个高频元素呢。
而且使用大顶堆就要把所有元素都进行排序,那能不能只排序k个元素呢?
所以我们要用小顶堆,因为要统计最大前k个元素,只有小顶堆每次将最小的元素弹出,最后小顶堆里积累的才是前k个最大元素。
寻找前k个最大元素流程如图所示:(图中的频率只有三个,所以正好构成一个大小为3的小顶堆,如果频率更多一些,则用这个小顶堆进行扫描)


// 定义一个名为 Solution 的类
class Solution {
// 定义一个公共方法,返回一个整数数组,该方法接收两个参数:一个整数数组 nums 和一个整数 k
public int[] topKFrequent(int[] nums, int k) {
// 创建一个优先级队列 pq,用于存储整数数组,队列的排序规则是从大到小(根据数组的第二个元素)
// 这是为了避免使用复杂的 API 操作,因为优先级队列的特性是队首元素总是最小的(或者最大的,取决于排序规则)
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
// 创建一个大小为 k 的整数数组 res,用于存储结果 int[] res = new int[k]; // 创建一个哈希映射 map,用于记录每个元素的出现次数 Map<Integer, Integer> map = new HashMap<>(); // 遍历输入数组 nums,统计每个元素的出现次数,并存储在哈希映射 map 中 for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1); // 遍历哈希映射的 entrySet,将每个元素及其出现次数转化为数组形式,并加入优先级队列 pq for(var x : map.entrySet()) { int[] tmp = new int[2]; tmp[0] = x.getKey(); // 当前元素的键(数字) tmp[1] = x.getValue(); // 当前元素的值(出现次数) pq.offer(tmp); // 将转化后的数组加入优先级队列 pq // 如果优先级队列的大小超过了 k,则移除队首元素(即出现次数最少的元素) if(pq.size() > k) { pq.poll(); } } // 从优先级队列 pq 中取出前 k 个元素(即出现次数最多的 k 个元素),并存入结果数组 res for(int i = 0; i < k; i ++) { res[i] = pq.poll()[0]; // 取出的数组的第一个元素是数字本身,所以用 poll()[0] 获取这个数字 } // 返回结果数组 res return res;
}
}
这个代码的主要思路是利用优先级队列来存储出现次数最多的k个元素。由于优先级队列的特性,我们可以在添加新元素时保持队列的大小不超过k,同时保证了队首始终是出现次数最多的元素。这样,最后从队列中取出的就是出现次数最多的k个元素。


相关文章:
2024.1.23(347.前k个高频元素)
2024.1.23(347.前k个高频元素) 思路 这道题目主要涉及到如下三块内容: 1.要统计元素出现频率 2.对频率排序 3.找出前K个高频元素 首先统计元素出现的频率,这一类的问题可以使用map来进行统计。 然后是对频率进行排序,这里我们可以使用一种…...
MySQL对数据库的操作
前腰:本节只是的数据库本身进行增删查改、备份、恢复等操作,而不是对数据库内的数据表做操作,还请您区分好这两点。 1.创建数据库 # 创建数据库的语法形式 CREATE DATABASE [IF NOT EXISTS] database_name [create_specification]# 大写的是…...
解决Unity WebGLInput插件全屏输入的问题
unity webgl的中文输入插件WebglInput在全屏的时候会出现无法输入中文/输入的英文会字母出现在光标后面/什么都输入不了的等无法正常使用的情况。 插件官网作者给出了unity的2017,2018,2019版本的全屏输入解决方法。 最新插件下载地址:http…...
Android14实战:调整A2DP音量曲线(五十三)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...
vector讲解
在学习玩string后我们开始学习vector,本篇博客将对vector进行简单的介绍,还会对vector一些常用的函数进行讲解 vector的介绍 实际上vector就是一个数组的数据结构,但是vector是由C编写而成的,他和数组也有本质上的区别ÿ…...
nvm 配置淘宝镜像失效,以及安装node后 npm-v 无效
win11 nvm版本 1.1.4 和1.1.7和1.1.12(目前最新版本24年 一月二十三日) 以上nvm版本都会出现一下问题, 从https://github.com/coreybutler/nvm-windows/releases 下载nvm安装包如下图 傻瓜式安装后,不用去配置环境变量&#…...
【Android Gradle 插件】Gradle 基础配置 ④ ( Gradle Wrapper 配置作用 | Gradle 下载的依赖库存放位置 )
一、Gradle Wrapper 配置作用 gradle wrapperdistributionBaseGRADLE_USER_HOME distributionPathwrapper/dists distributionUrlhttps\://services.gradle.org/distributions/gradle-6.7.1-bin.zip zipStoreBaseGRADLE_USER_HOME zipStorePathwrapper/distsGradle Wrapper 配…...
Deepin_Ubuntu_查看树形目录结构(tree)
Linux系统(Deepin、Ubuntu)中,可以使用tree命令来查看树形目录结构,下面是一些示例: 查看当前目录的树形结构: tree查看指定目录的树形结构,例如/etc/X11/fonts目录: tree /etc/X…...
Java Excel分割成许多小文件
最近在处理excel,数据很多,需要将excel拆分成许多小块,并保留原来的格式,于是写了该算法,并能保留原来的样式,使用很简单: Sheet splitSheet ExcelUtil.split(sheet, 0, 20, 5, 8); 传入开始…...
【心得】java从CC1链入门CC链个人笔记
来劲了,感觉离真正的CTF又近了一步。 本文仅从一个萌新的角度去谈,如有纰漏,纯属蒟蒻。 目录 CC链概念 CC链学习前置知识 CC1链 Version1 Version2 Version3 CC链概念 CC链 Commons Collections apache组织发布的开源库 里面主要对…...
Django migration 新增外键的坑
TL;DR 永远不要相信 makemigrations! migrate 之前一定好好看看 migrate 了啥东西,必要时手动修改生成的 migrate 文件。 最好把db的更新与服务代码更新解耦 场景 先描述下场景: 现在有两个表,一个是 question,一…...
相关系数(皮尔逊相关系数和斯皮尔曼相关系数)
本文借鉴了数学建模清风老师的课件与思路,可以点击查看链接查看清风老师视频讲解:5.1 对数据进行描述性统计以及皮尔逊相关系数的计算方法_哔哩哔哩_bilibili 注:直接先看 ( 三、两个相关系数系数的比较 ) 部分&#x…...
了解 Vite 插件
众所周知 Vite 是基于 Rollup 的构建工具,Vite 插件为了优化、扩展项目构建系统功能的工具。 比如 vite-plugin-eslint 为我们提供了代码分析的功能,帮助我们在开发过程中的风格一致性。 简单示例 本文中的示例是基于 Vite Vue3.x TypeScript 来实现…...
算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)
算法竞赛基础:双向链表 本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。 双向链表的结构 一般来说,普通的链表结构是这样的: struct node {int num;node *next; }next指针指向下一个链表ÿ…...
openssl3.2/test/certs - 019 - ca-nonca trust variants: +serverAuth, +anyEKU
文章目录 openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAuth, anyEKU概述笔记 ca-nonca.pem from exp 016openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAuth, anyEKUEND openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAu…...
Unity SRP 管线【第五讲:URP烘培光照】
本节,我们将跟随数据流向讲解UEP管线中的烘培光照。 文章目录 一、URP烘培光照1. 搭建场景2. 烘培光照参数设置MixedLight光照设置:直观感受 Lightmapping Settings参数设置: 3. 我们如何记录次表面光源颜色首先我们提取出相关URP代码&#…...
Mysql运维篇(一) 日志类型
一路走来,所有遇到的人,帮助过我的、伤害过我的都是朋友,没有一个是敌人,如有侵权请留言,我及时删除。 一、mysql相关日志 首先,我们能接触到的,一般我们排查慢查询时,会去看慢查询日志。如果做过数据备份会恢复的,可能接触或用过BinLog。那还有其他的吗?对MySQL原理…...
【C语言】结构体与内存操作函数 总结
结构体 一、结构体简介 C 语言内置的数据类型,除了最基本的几种原始类型,只有数组属于复合类型,可以同时包含多个值,但是只能包含相同类型的数据,实际使用中并不够用。 实际使用中,主要有下面两种情况&a…...
第12章_集合框架(Collection接口,Iterator接口,List,Set,Map,Collections工具类)
文章目录 第12章_集合框架本章专题与脉络1. 集合框架概述1.1 生活中的容器1.2 数组的特点与弊端1.3 Java集合框架体系1.4 集合的使用场景 2. Collection接口及方法2.1 添加2.2 判断2.3 删除2.4 其它 3. Iterator(迭代器)接口3.1 Iterator接口3.2 迭代器的执行原理3.3 foreach循…...
C语言进阶——数据结构之链表(续)
前言 hello,大家好呀,我是Humble,本篇博客承接之前的C语言进阶——数据结构之链表 的内容(没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~),上次我们重点说了链表中…...
Phi-3-mini-4k-instruct-gguf多场景:覆盖个人提效、团队协作、客户支持全链路
Phi-3-mini-4k-instruct-gguf多场景:覆盖个人提效、团队协作、客户支持全链路 1. 认识Phi-3-mini-4k-instruct-gguf Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本。这个开箱即用的工具特别适合处理日常工作中的文本任务,…...
DLSS Swapper智能工具:游戏性能优化与版本管理完全指南
DLSS Swapper智能工具:游戏性能优化与版本管理完全指南 【免费下载链接】dlss-swapper 项目地址: https://gitcode.com/GitHub_Trending/dl/dlss-swapper DLSS Swapper是一款专为游戏玩家设计的深度学习超级采样(DLSS)版本管理工具,能够自动扫描…...
5分钟搞定:Mac用户制作Windows启动盘的终极指南
5分钟搞定:Mac用户制作Windows启动盘的终极指南 【免费下载链接】windiskwriter 🖥 A macOS app that creates bootable USB drives for Windows. 🛠 Patches Windows 11 to bypass TPM and Secure Boot requirements. 项目地址: https://g…...
Vue3前端集成Gemma-3-12B-IT:构建智能聊天界面
Vue3前端集成Gemma-3-12B-IT:构建智能聊天界面 用最简单的方式,让你的Vue3项目拥有智能对话能力 1. 为什么要在Vue3中集成智能聊天功能 现在很多网站和应用都需要智能对话功能,不管是客服系统、学习助手还是内容创作工具。Gemma-3-12B-IT作为…...
墨语灵犀助力软件测试:智能测试用例生成与缺陷报告分析
墨语灵犀助力软件测试:智能测试用例生成与缺陷报告分析 作为一名在软件测试领域摸爬滚打多年的工程师,我深知这份工作的“痛”与“乐”。痛的是,面对动辄几十上百页的需求文档,手动编写测试用例的枯燥与耗时;乐的是&a…...
XHS-Downloader:构建高效采集流程的无水印内容批量管理方案
XHS-Downloader:构建高效采集流程的无水印内容批量管理方案 【免费下载链接】XHS-Downloader 小红书(XiaoHongShu、RedNote)链接提取/作品采集工具:提取账号发布、收藏、点赞、专辑作品链接;提取搜索结果作品、用户链接…...
Windows 11 + CUDA 11.7 环境下,TensorRT 8.5.2.2 保姆级安装与配置避坑指南
Windows 11 CUDA 11.7 环境下 TensorRT 8.5.2.2 终极安装指南 刚接触深度学习推理优化的开发者,往往会在环境配置阶段耗费大量时间。TensorRT作为NVIDIA官方推出的高性能推理库,能够显著提升模型在NVIDIA GPU上的运行效率。本文将手把手带你完成Windows…...
Pikachu靶场实战:File Inclusion漏洞利用与防御全解析
1. File Inclusion漏洞初探:从理论到靶场实战 文件包含(File Inclusion)漏洞是Web安全领域最常见的漏洞类型之一,它允许攻击者通过参数控制加载服务器上的任意文件。想象一下,你家的门锁如果设计不当,小偷只…...
FUTURE POLICE语音模型重装系统后快速恢复部署指南
FUTURE POLICE语音模型重装系统后快速恢复部署指南 重装系统这事儿,对开发者来说,有时候就跟电脑的“大扫除”一样,图个干净利落。但扫除完,看着空空如也的桌面和命令行,要重新把那些吃饭的家伙——比如你正在跑的FUT…...
UE5伤害系统避坑指南:Damage Type没用好?你的Apply Damage可能白写了
UE5伤害系统深度解析:如何用Damage Type构建高扩展性战斗机制 在虚幻引擎5的游戏开发中,伤害系统是战斗机制的核心支柱。许多开发者习惯性地将注意力集中在Damage Amount这个数值上,却忽视了Damage Type这个能够赋予游戏深度和多样性的强大工…...
