在做题中学习(78):数组中第K个最大元素

解法:快速选择算法

说明:堆排序也是经典解决topK问题的算法,但时间复杂度为:O(NlogN)

而将要介绍的快速选择算法的时间复杂度为: O(N)

先看我的前两篇文章,分别学习:数组分三块,随机选择基准值的思想。会的话直接看就完事了

思路:

解惑:

1.a,b,c是什么意思?

        a,b,c分别是<key, = key, >key 所代表的区间中值的个数

2.如何判断?

        看落在哪个区间,c区间全是>key的,所以如果落在这个区间,就只在这个区间递归即可。

        而如果 b + c >=k 说明,k > c了也就是不在c区间,而第k个元素是在b这个区间中,而b是= key的,所以直接返回key即可。

        如果都不是,说明k > b + c了,所以k是很大的数字,那第k大就是一个很小的数字,肯定落在a区间,而因为现在我们跳过了 b+c个元素,所以要找的其实是第k - b - c个元素!

附上完整代码:

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));return qselect(nums,0,nums.size()-1,k);}int qselect(vector<int>& nums,int l,int r,int k){//返回条件if(l >= r)return nums[l];//选择基准元素int key = GetRandomKey(nums,l,r);int left = l-1,right = r+1;//快排(数组分三块)的一趟for(int i = l;i<nums.size();){if(nums[i] < key)swap(nums[++left],nums[i++]);else if(nums[i] == key)i++;else if(nums[i] > key){if(i == right)break;swap(nums[--right],nums[i]);}}//分情况讨论int c = r - right + 1,b = right - left - 1;if(c >= k) return qselect(nums,right,r,k);else if(b + c >= k) return key;else    return qselect(nums,l,left,k-b-c);}int GetRandomKey(vector<int>& nums,int l,int r){int randnum = rand();return nums[randnum % (r - l + 1) + l];}
};

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

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

相关文章

分布式事务的前世今生-纯理论

一个可用的复杂的系统总是从可用的简单系统进化而来。反过来这句话也正确: 从零开始设计的复杂的系统从来都用不了&#xff0c;也没办法让它变的可用。 --John Gal 《系统学》 1975 1. 事务的概念 百科&#xff1a; 事务&#xff08;Transaction&#xff09;&#xff0c;一般是…

MySQL 服务无法启动

常见原因: 检查端口占用&#xff1a; 使用命令行工具&#xff08;如netstat&#xff09;来检查3306端口是否已被其他程序占用,输入netstat -ano&#xff08;Windows&#xff09;或netstat -tulnp | grep 3306&#xff08;Linux/Mac&#xff09;来查找3306端口的占用情况。如果…

基于Node.js的后端服务基础模块及应用

使用generator-express-no-stress-typescript脚手架工具创建一个图片上传服务的模板工程&#xff0c;执行如下指令&#xff1a; npm config set registry https://registry.npmmirror.com yo express-no-stress-typescript uploadService 可以看到后端框架如下&#xff1a; 先…

Hadoop生态圈框架部署 伪集群版(八)- Sqoop安装与配置

文章目录 前言一、Sqoop安装与配置&#xff08;手动安装配置&#xff09;1. 下载Sqoop2. 解压Sqoop安装包2.1 解压2.2 重命名 3. 配置Sqoop3.1 配置Sqoop环境变量3.2 修改 sqoop-env.sh 配置文件3.3 配置jar包3.3.1 配置MySQL驱动jar包3.3.2 配置commons-lang-2.6.jar包 4. 测试…

视频编辑技术:一键生成混剪视频的AI技术应用

随着视频内容的爆炸式增长&#xff0c;视频编辑技术也在不断进步。本文将探讨如何利用AI技术&#xff0c;实现一键生成混剪视频&#xff0c;并自动添加配音和字幕&#xff0c;以提高视频编辑的效率和质量。 AI技术在视频编辑中的应用 AI技术在视频编辑领域的应用越来越广泛&am…

笔记本外接显示屏没声音

1、笔记本正常有声音&#xff0c;但是外接显示屏后没有声音了怎么回事呢&#xff1f;原来外接显示屏后笔记本的声音输出会自动选择显示屏的音频输出&#xff0c;但是显示屏可能没有声音输出所以导致笔记本没有声音。 2、解决办法&#xff1a;打开笔记本设置&#xff0c;选择声…

Linux其二设置端口号,静态ip以及命令

目录 1、VI编辑器 【linux版本的文本文件】 2&#xff09; 补充的vi编辑器的其他内容(了解) 2、ln 连接的意思 link的缩写 3、文件的查看 【重点】 4、压缩与解压&#xff08;重点&#xff09; 5、find 查找命令 6、which & whereis 作用是一样的&#xff0c;表示某…

飞飞5.4游戏源码(客户端+服务端+工具完整源代码+5.3fix+5.4patch+数据库可编译进游戏)

飞飞5.4游戏源码&#xff08;客户端服务端工具完整源代码5.3fix5.4patch数据库可编译进游戏&#xff09; 下载地址&#xff1a; 通过网盘分享的文件&#xff1a;【源码】飞飞5.4游戏源码&#xff08;客户端服务端工具完整源代码5.3fix5.4patch数据库可编译进游戏&#xff09; 链…

【Linux】进程间通信 -- System V 消息队列

前言 上节Linux学习&#xff0c;我们学习了System V的共享内存&#xff0c;本节我们学习System V 的另一种通信方式 — 消息队列 文章目录 前言一. 消息队列的原理二.创建消息队列二. 查看消息队列三. 删除消息队列四. 读写数据结束语 一. 消息队列的原理 消息队列的本质同共享…

Elasticsearch入门之HTTP基础操作

RESTful REST 指的是一组架构约束条件和原则。满足这些约束条件和原则的应用程序或设计就是 RESTful。Web 应用程序最重要的 REST 原则是&#xff0c;客户端和服务器之间的交互在请求之间是无状态的。从客户端到服务器的每个请求都必须包含理解请求所必需的信息。如果服务器在…

4.模块化技术之子程序

总学习目录请点击下面连接 SAP ABAP开发从0到入职&#xff0c;冷冬备战-CSDN博客 目录 ​编辑 1.模块化基础和概述 使用模块化有什么好处 两大类模块化技术 程序局部的模块化 SAP系统内全局模块化 封装有什么好处&#xff1f; 2.子程序模块化 三种传递类型 子程序结构…

69 mysql 中 is null 的实现

前言 Mysql 中我们偶尔会用到 字段为 NULL 的情况 这时候 我们只能使用查询 “select * from tz_test_02 where field1 is null;” 来进行 field1 字段为 null 的行的查询 然后如果是使用 “select * from tz_test_02 where field1 null;” 你会发现查询 不出数据 但是如…

51c嵌入式~单片机合集3

我自己的原文哦~ https://blog.51cto.com/whaosoft/12581900 一、STM32代码远程升级之IAP编程 IAP是什么 有时项目上需要远程升级单片机程序&#xff0c;此时需要接触到IAP编程。 IAP即为In Application Programming&#xff0c;解释为在应用中编程&#xff0c;用户自己的程…

网上图书购物管理系统|Java|SSM|VUE| 前后端分离

【一】可以提供远程部署安装&#xff0c;包扩环境 【二】提供软件相关的安装包 【三】如果需要提供java入门资料可咨询 【技术栈】 1⃣️&#xff1a;架构: B/S、MVC 2⃣️&#xff1a;系统环境&#xff1a;Windowsh/Mac 3⃣️&#xff1a;开发环境&#xff1a;IDEA、JDK1.8、M…

Python酷库之旅-第三方库Pandas(264)

目录 一、用法精讲 1251、pandas.tseries.offsets.WeekOfMonth.is_year_end方法 1251-1、语法 1251-2、参数 1251-3、功能 1251-4、返回值 1251-5、说明 1251-6、用法 1251-6-1、数据准备 1251-6-2、代码示例 1251-6-3、结果输出 1252、pandas.tseries.offsets.Las…

“为您的家电穿上防震铠甲:优质电器缓冲器

在地震频发地区或日常生活中&#xff0c;确保家电的安全和稳定至关重要。为了防止地震、意外碰撞或其他外力对家电造成损害&#xff0c;采用优质的电器缓冲器就像是为家电穿上了一层坚固的“防震铠甲”。这不仅能够有效减少因震动导致的损坏风险&#xff0c;还能显著延长家电的…

全连接层与链式求导法则在神经网络中的应用

目录 ​编辑 引言 全连接层的工作原理 前向传播 反向传播 链式求导法则及其在神经网络中的应用 链式求导法则 应用于全连接层 计算梯度 结论 引言 在深度学习领域&#xff0c;全连接层&#xff08;Fully Connected Layer&#xff0c;FC&#xff09;和链式求导法则是…

基于框架的逻辑回归:原理、实现与应用

目录 ​编辑 逻辑回归原理 损失函数与优化 正则化 基于框架的实现 1. 数据预处理 2. 模型初始化与训练 3. 模型评估与调优 4. 特征缩放 逻辑回归的应用 信用评分 医疗诊断 垃圾邮件识别 推荐系统 结论 在机器学习领域&#xff0c;逻辑回归是一种基础且强大的分类…

【SpringBoot】Day11-10 yml文件配置

三种配置文件 前面我们一直使用springboot项目创建完毕后自带的application.properties进行属性的配置&#xff0c;那其实呢&#xff0c;在springboot项目当中是支持多种配置方式的&#xff0c;除了支持properties配置文件以外&#xff0c;还支持另外一种类型的配置文件&#x…

强化学习新突破:情节记忆与奖励机制引领多智能体协作

简介 本推文介绍了韩国科学技术院发表在人工智能顶会ICLR 2024上的论文《Efficient Episodic Memory Utilization of Cooperative Multi-Agent Reinforcement Learning》。该论文提出创新性高效情节记忆利用&#xff08;Efficient Episodic Memory Utilization&#xff0c;EMU…