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

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个高频元素) 思路 这道题目主要涉及到如下三块内容&#xff1a; 1.要统计元素出现频率 2.对频率排序 3.找出前K个高频元素 首先统计元素出现的频率&#xff0c;这一类的问题可以使用map来进行统计。 然后是对频率进行排序&#xff0c;这里我们可以使用一种…...

MySQL对数据库的操作

前腰&#xff1a;本节只是的数据库本身进行增删查改、备份、恢复等操作&#xff0c;而不是对数据库内的数据表做操作&#xff0c;还请您区分好这两点。 1.创建数据库 # 创建数据库的语法形式 CREATE DATABASE [IF NOT EXISTS] database_name [create_specification]# 大写的是…...

解决Unity WebGLInput插件全屏输入的问题

unity webgl的中文输入插件WebglInput在全屏的时候会出现无法输入中文/输入的英文会字母出现在光标后面/什么都输入不了的等无法正常使用的情况。 插件官网作者给出了unity的2017&#xff0c;2018&#xff0c;2019版本的全屏输入解决方法。 最新插件下载地址&#xff1a;http…...

Android14实战:调整A2DP音量曲线(五十三)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...

vector讲解

在学习玩string后我们开始学习vector&#xff0c;本篇博客将对vector进行简单的介绍&#xff0c;还会对vector一些常用的函数进行讲解 vector的介绍 实际上vector就是一个数组的数据结构&#xff0c;但是vector是由C编写而成的&#xff0c;他和数组也有本质上的区别&#xff…...

nvm 配置淘宝镜像失效,以及安装node后 npm-v 无效

win11 nvm版本 1.1.4 和1.1.7和1.1.12&#xff08;目前最新版本24年 一月二十三日&#xff09; 以上nvm版本都会出现一下问题&#xff0c; 从https://github.com/coreybutler/nvm-windows/releases 下载nvm安装包如下图 傻瓜式安装后&#xff0c;不用去配置环境变量&#…...

【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系统&#xff08;Deepin、Ubuntu&#xff09;中&#xff0c;可以使用tree命令来查看树形目录结构&#xff0c;下面是一些示例&#xff1a; 查看当前目录的树形结构&#xff1a; tree查看指定目录的树形结构&#xff0c;例如/etc/X11/fonts目录&#xff1a; tree /etc/X…...

Java Excel分割成许多小文件

最近在处理excel&#xff0c;数据很多&#xff0c;需要将excel拆分成许多小块&#xff0c;并保留原来的格式&#xff0c;于是写了该算法&#xff0c;并能保留原来的样式&#xff0c;使用很简单&#xff1a; Sheet splitSheet ExcelUtil.split(sheet, 0, 20, 5, 8); 传入开始…...

【心得】java从CC1链入门CC链个人笔记

来劲了&#xff0c;感觉离真正的CTF又近了一步。 本文仅从一个萌新的角度去谈&#xff0c;如有纰漏&#xff0c;纯属蒟蒻。 目录 CC链概念 CC链学习前置知识 CC1链 Version1 Version2 Version3 CC链概念 CC链 Commons Collections apache组织发布的开源库 里面主要对…...

Django migration 新增外键的坑

TL;DR 永远不要相信 makemigrations&#xff01; migrate 之前一定好好看看 migrate 了啥东西&#xff0c;必要时手动修改生成的 migrate 文件。 最好把db的更新与服务代码更新解耦 场景 先描述下场景&#xff1a; 现在有两个表&#xff0c;一个是 question&#xff0c;一…...

相关系数(皮尔逊相关系数和斯皮尔曼相关系数)

本文借鉴了数学建模清风老师的课件与思路&#xff0c;可以点击查看链接查看清风老师视频讲解&#xff1a;5.1 对数据进行描述性统计以及皮尔逊相关系数的计算方法_哔哩哔哩_bilibili 注&#xff1a;直接先看 &#xff08; 三、两个相关系数系数的比较 &#xff09; 部分&#x…...

了解 Vite 插件

众所周知 Vite 是基于 Rollup 的构建工具&#xff0c;Vite 插件为了优化、扩展项目构建系统功能的工具。 比如 vite-plugin-eslint 为我们提供了代码分析的功能&#xff0c;帮助我们在开发过程中的风格一致性。 简单示例 本文中的示例是基于 Vite Vue3.x TypeScript 来实现…...

算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)

算法竞赛基础&#xff1a;双向链表 本文将会介绍在算法竞赛中双向链表的几种使用方式&#xff0c;适合有一定基础的人阅读。 双向链表的结构 一般来说&#xff0c;普通的链表结构是这样的&#xff1a; struct node {int num;node *next; }next指针指向下一个链表&#xff…...

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烘培光照】

本节&#xff0c;我们将跟随数据流向讲解UEP管线中的烘培光照。 文章目录 一、URP烘培光照1. 搭建场景2. 烘培光照参数设置MixedLight光照设置&#xff1a;直观感受 Lightmapping Settings参数设置&#xff1a; 3. 我们如何记录次表面光源颜色首先我们提取出相关URP代码&#…...

Mysql运维篇(一) 日志类型

一路走来,所有遇到的人,帮助过我的、伤害过我的都是朋友,没有一个是敌人,如有侵权请留言,我及时删除。 一、mysql相关日志 首先,我们能接触到的,一般我们排查慢查询时,会去看慢查询日志。如果做过数据备份会恢复的,可能接触或用过BinLog。那还有其他的吗?对MySQL原理…...

【C语言】结构体与内存操作函数 总结

结构体 一、结构体简介 C 语言内置的数据类型&#xff0c;除了最基本的几种原始类型&#xff0c;只有数组属于复合类型&#xff0c;可以同时包含多个值&#xff0c;但是只能包含相同类型的数据&#xff0c;实际使用中并不够用。 实际使用中&#xff0c;主要有下面两种情况&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&#xff0c;大家好呀&#xff0c;我是Humble&#xff0c;本篇博客承接之前的C语言进阶——数据结构之链表 的内容&#xff08;没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~&#xff09;&#xff0c;上次我们重点说了链表中…...

MiniCPM-o-4.5-nvidia-FlagOS部署运维:使用Docker Compose管理多服务依赖

MiniCPM-o-4.5-nvidia-FlagOS部署运维&#xff1a;使用Docker Compose管理多服务依赖 你是不是也遇到过这种情况&#xff1f;想部署一个AI模型&#xff0c;发现它依赖一堆东西&#xff1a;模型服务本身、数据库、缓存、可能还有别的辅助工具。一个个手动去装、去配置、去启动&…...

如何通过Snap Hutao实现原神游戏决策的智能化?

如何通过Snap Hutao实现原神游戏决策的智能化&#xff1f; 【免费下载链接】Snap.Hutao 实用的开源多功能原神工具箱 &#x1f9f0; / Multifunctional Open-Source Genshin Impact Toolkit &#x1f9f0; 项目地址: https://gitcode.com/GitHub_Trending/sn/Snap.Hutao …...

一键搭建AI对话系统:通义千问1.5-1.8B-Chat-GPTQ-Int4镜像使用指南

一键搭建AI对话系统&#xff1a;通义千问1.5-1.8B-Chat-GPTQ-Int4镜像使用指南 想快速拥有一个属于自己的AI对话助手吗&#xff1f;今天要介绍的这个方法&#xff0c;可能比你想象中简单得多。不用折腾复杂的模型下载&#xff0c;不用配置繁琐的运行环境&#xff0c;更不用写一…...

腾讯混元翻译模型HY-MT1.5-1.8B:免费开源,企业级翻译解决方案

腾讯混元翻译模型HY-MT1.5-1.8B&#xff1a;免费开源&#xff0c;企业级翻译解决方案 1. 引言 1.1 为什么选择HY-MT1.5-1.8B 在全球化的商业环境中&#xff0c;语言障碍成为企业拓展国际市场的首要挑战。腾讯混元团队推出的HY-MT1.5-1.8B翻译模型&#xff0c;以其18亿参数的…...

效率倍增:基于快马平台集成最新openclaw构建自动化采集工具

最近在做一个数据采集项目时&#xff0c;发现手动写爬虫实在太费时间了。每次都要重复处理请求头、代理设置、数据清洗这些基础工作&#xff0c;效率特别低。后来发现了openclaw这个工具包的新版本&#xff0c;正好结合InsCode(快马)平台快速搭建了一个自动化采集工具&#xff…...

别再纠结了!.NET后台任务调度,Hangfire和Quartz.NET到底怎么选?

Hangfire与Quartz.NET深度抉择指南&#xff1a;从业务场景到技术实现的精准匹配 在.NET生态系统中&#xff0c;后台任务调度是几乎所有企业级应用都无法绕开的核心需求。无论是电商平台的订单状态更新、金融系统的日终批处理&#xff0c;还是内容管理系统的定时数据同步&#x…...

【ROS2 基础】ROS2与Colcon核心指令速查手册与避坑指南

为了在 ROS2 的日常开发中提升效率&#xff0c;本文为您整理了一份结构化的核心指令速查清单。去除了冗长的理论&#xff0c;直击实战痛点&#xff0c;并附带了多平台差异、性能优化数据以及常见报错的修复方案。 文章目录[TOC]一、 快速入门&#xff1a;3步跑通基础流程二、 版…...

石油勘探中的地震波“翻译官”:如何读懂时距曲线图里的地下秘密?

石油勘探中的地震波“翻译官”&#xff1a;如何读懂时距曲线图里的地下秘密&#xff1f; 站在戈壁滩的勘探营地&#xff0c;望着屏幕上那些看似杂乱的波形曲线&#xff0c;刚入行的地质工程师小李皱起了眉头。"这些弯弯曲曲的线条&#xff0c;到底在诉说什么样的地下故事&…...

高效突破:Cursor Pro功能优化与多场景应用指南

高效突破&#xff1a;Cursor Pro功能优化与多场景应用指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your trial requ…...

Pixel Couplet Gen应用场景:微信小程序开发者如何复用像素皇城UI组件

Pixel Couplet Gen应用场景&#xff1a;微信小程序开发者如何复用像素皇城UI组件 1. 项目背景与价值 Pixel Couplet Gen是一款融合传统春节文化与现代像素艺术风格的创新应用。作为微信小程序开发者&#xff0c;您可以直接复用其UI组件库&#xff0c;快速构建具有以下特点的应…...