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语言进阶之数据结构 找到那篇文章并阅读后在回来哦~),上次我们重点说了链表中…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
【版本控制】GitHub Desktop 入门教程与开源协作全流程解析
目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork(创建个人副本)步骤 2: Clone(克隆…...
