C++力扣题目347--前k个高频元素

给你一个整数数组 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 个高频元素的集合是唯一的

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

思路:

这道题目主要涉及到如下三块内容:

  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的小顶堆,如果频率更多一些,则用这个小顶堆进行扫描)

347.前K个高频元素

我们来看一下C++代码:

class Solution {
public:// 小顶堆class mycomparison {public://仿函数,来指定优先级队列的排序规则bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆,大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆,扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

  • 时间复杂度: O(nlogk)
  • 空间复杂度: O(n)

#拓展

大家对这个比较运算在建堆时是如何应用的,为什么左大于右就会建立小顶堆,反而建立大顶堆比较困惑。

确实 例如我们在写快排的cmp函数的时候,return left>right 就是从大到小,return left<right 就是从小到大。

优先级队列的定义正好反过来了,可能和优先级队列的源码实现有关(我没有仔细研究),我估计是底层实现上优先队列队首指向后面,队尾指向最前面的缘故!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659680.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

别再写一堆的 for 循环了!Java 8 中的 Stream 轻松遍历树形结构,是真的牛逼!

可能平常会遇到一些需求&#xff0c;比如构建菜单&#xff0c;构建树形结构&#xff0c;数据库一般就使用父id来表示&#xff0c;为了降低数据库的查询压力&#xff0c;我们可以使用Java8中的Stream流一次性把数据查出来&#xff0c;然后通过流式处理。 我们一起来看看&#x…

Nginx直播服务器搭建及推拉流测试

文章目录 前言一、搭建 Nginx 直播服务器1、安装 Nginx 依赖2、下载并解压源码①、下载并解压 nginx-http-flv-module 直播模块源码②、下载并解压 Nginx 源码 3、编译安装4、配置 rtmp 服务①、添加 rtmp 服务②、验证配置 二、推流、拉流测试1、ffmepg 推流2、VLC 拉流 前言 …

案例224:基于微信小程序的餐厅点餐系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

基于Java Swing的图书管理系统

一、项目总体架构 本项目基于Java Swing框架&#xff0c;数据库采用的是MySQL。项目文件夹如下&#xff1a; 二、项目截图 1.登录和注册界面 2.用户界面 3.管理员管理图书类别 4.管理员管理书籍 5.管理员管理用户 项目总体包括源代码和课程论文&#xff0c;需要源码的…

OCP NVME SSD规范解读-3.NVMe管理命令-part2

NVMe-AD-8&#xff1a;在某些情况下&#xff08;如Sanitize命令、Format NVM命令或TCG Revert方法后数据被清除&#xff09;&#xff0c;设备应允许读取已清除的LBAs而不产生错误&#xff0c;并在最后一次清除完成后&#xff0c;对未写入LBAs的读取返回所有零值给主机 NVMe-AD…

教育数字化:重塑新时代教育模式及教育理念

2023年&#xff0c;是加快教育强国建设新篇章的重要一年。在这一年里&#xff0c;ChatGTP、教育数字化、自主学习等成为年度教育热词&#xff0c;“教育数字化”&#xff0c;不仅是今年教育发展的关键词&#xff0c;同时也是重塑新时代教育模式及理念的基础。 2023年2月&#…

IPEmotion数据采集软件功能介绍

IPEmotion作为IPETRONIK的软件产品&#xff0c;主要应用于车辆测试和不同的实验室测试系统&#xff0c;能够满足各种测量需求。通过专业化的数据采集软件IPEmotion&#xff0c;我们可实现完整的数据采集过程&#xff0c;包括&#xff1a;配置数据采集设备&#xff1b;使用不同的…

C语言实现RSA算法加解密

使用c语言实现了RSA加解密算法&#xff0c;可以加解密文件和字符串。 rsa算法原理 选择两个大素数p和q&#xff1b;计算n p * q;计算φ(n)(p-1)(q-1)&#xff1b;选择与φ(n)互素的整数d&#xff1b;由de1 mod φ(n)计算得到e&#xff1b;公钥是(e, n), 私钥是(d, n);假设明…

c# listbox 添加图标和文字

给listbox 添加 DrawItem 事件 private void listBox1_DrawItem(object sender, DrawItemEventArgs e){int index e.Index;//获取当前要进行绘制的行的序号&#xff0c;从0开始。Graphics g e.Graphics;//获取Graphics对象。Rectangle bound e.Bounds;//获取当前要绘制的行的…

CorelCAD各版本安装指南

下载链接 https://pan.baidu.com/s/1v0VgYRaaRRUeAgJC__0rPw?pwd0531 1.鼠标右击【CorelCAD2023(64bit)】压缩包&#xff08;win11及以上系统需先点击“显示更多选项”&#xff09;选择【解压到 CorelCAD2023(64bit)】。 2.打开解压后的文件夹&#xff0c;鼠标右击【CorelCA…

Armpro脱壳软件搭建教程附源代码

PHP8.0版本&#xff0c;数据库8.0版本 1.配置注册机文件&#xff0c;打开将arm.zip/res目录下&#xff0c;mt管理器搜索将其全部修改为你自己的域名或者是服务器IP 2.然后建立数据库 数据库账号arm 数据库用户名arm 数据库密码EsZfXY4tD3h2NNA4 3.导入数据库 4.配置Redi…

TCP状态转换/ 半连接/ 端口复用代码实现

三次挥手的时候的状态转换 TCP&#xff08;Transmission Control Protocol&#xff09;的三次握手是建立TCP连接的过程。在三次握手中&#xff0c;涉及到的状态转换如下&#xff1a; Closed&#xff08;关闭状态&#xff09;&#xff1a; 初始状态&#xff0c;表示没有任何连接…

【没有哪个港口是永远的停留~论文简读】Panoptic SegFormer

Panoptic SegFormer 原文&#xff1a;https://arxiv.org/pdf/2109.03814.pdf 代码&#xff1a;GitHub - zhiqi-li/Panoptic-SegFormer: This is the official repo of Panoptic SegFormer [CVPR22] 在全景分割中&#xff0c;图像内容可分为things和stuff两类。 things是可计…

Flink1.17实战教程(第七篇:Flink SQL)

系列文章目录 Flink1.17实战教程&#xff08;第一篇&#xff1a;概念、部署、架构&#xff09; Flink1.17实战教程&#xff08;第二篇&#xff1a;DataStream API&#xff09; Flink1.17实战教程&#xff08;第三篇&#xff1a;时间和窗口&#xff09; Flink1.17实战教程&…

根据commitID删除某一次提交

1.查看提交历史 git log --prettyoneline2.找到需要删除的那个commit,然后找到上次提交的commitID 比如想要删除下面这一条 我们找到上次提交的commitID 3.执行rebase git rebase -i efa11da0a684977bf8ac047ebb803e2ded2063a4 进入编辑状态显示如下 将需要删除的那个提交前…

汇编语言学习中的Dosbox自动配置方法

学到期末才发现可以自动配置 一、先找到dosbox的下载/安装路径 二、打开其下的Dosbox *.**(这里是版本号) Options.bat 三、在其打开的文件的最下面输入你经常打开dosbox要输入的内容 例如&#xff1a; mount c e:\masm c:

强化学习与推荐系统结合

强化学习与推荐系统结合&#xff0c;是在智能体的学习过程中&#xff0c;会根据外部反馈信息&#xff0c;改变自身状态&#xff0c;在根据自身状态进行决策&#xff0c;就是行动反馈&#xff0c;状态更新&#xff0c;在行动的循环。 深度强化学习推荐系统框架是基于强化学习的…

Github项目推荐:KaTeX

项目地址 GitHub - KaTeX/KaTeX: Fast math typesetting for the web. 项目描述 这是一个渲染公式的JavaScript库。有时候可能网页中需要写一些公式&#xff0c;但html本身并没有提供相应的标签。这个时候这个库就能派上用场了。 项目截图

MyBatis的基本使用及常见问题

MyBatis 前言MyBatis简介MyBatis快速上手Mapper代理开发增删改查环境准备配置文件完成增删改查查询添加修改删除 参数传递注解完成增删改查 前言 JavaWeb JavaWeb是用Java技术来解决相关Web互联网领域的技术栈。 MySQL数据库与SQL语言 MySQL&#xff1a;开源的中小型数据库。…

【理论】STM32定时器时间计算公式 +【实践】TIM中断1s计时一次

前言&#xff1a;定时器TIM的详细知识点见我的博文&#xff1a;11.TIM定时中断-CSDN博客 STM32定时器时间计算公式 公式解释&#xff1a; ARR&#xff08;TIM_Period&#xff09;&#xff1a;自动重装载值&#xff0c;是定时器溢出前的计数值 PSC&#xff08;TIM_Prescaler&…