【LeetCode热题100】分治-快排

本篇博客记录分治快排的4道题目:颜色分类、排序数组、数组中的第K个最大元素、数组中最小的N个元素(库存管理)。

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1,right = n;for(int i = 0 ; i < right ; ){if(nums[i] == 0) swap(nums[++left],nums[i++]);else if(nums[i] == 1) i++;else swap(nums[--right],nums[i]);}}
};

题目分析:本题的目的旨在将nums的元素0、1、2分成三块,打算采取三指针的方法。使用left、right、i三个变量,其中,left指向全0区间的最右侧,right指向全2区间的最左侧,i指向待扫描的下一个元素,这样就把整个区间划分为4块,包括:

[0,left]:全0区域

[left+1,i-1]:全1区域

[i,right-1]:待扫描的区域

[right,n-1]:全2区域

划分好区域后,刚开始让left指向nums的左侧,即left=-1,right指向nums的右侧,即right=n,i指向nums中的第一个元素,nums[i]就会有三种情况:0、1、2。对于这三种情况,处理的动作如下图:

class Solution {
public:int GetRef(vector<int>& nums , int left , int right){return nums[rand()%(right - left + 1) + left];}void _sortArray(vector<int>& nums, int left, int right){if(left >= right) return;int ref = GetRef(nums, left, right);int l = left - 1, r = right + 1, i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] == ref) i++;else swap(nums[--r],nums[i]);}//[left,l] [l+1,r-1] [r,right] _sortArray(nums,left,l);_sortArray(nums,r,right);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));_sortArray(nums, 0 , nums.size() - 1);return nums;}
};

题目分析:我们实现快排要用到“颜色分类”这道题的思想,向数组划分为三块,

这样迭代一次之后,[left+1,right-1]之间的元素已经排好,继续递归[0,left]和[right,n-1]即可。

在选择基准元素key时,我们可以使用随机的方式选取,ref = nums[rand()%(right-left+1)+left]。

class Solution {
public:int GetRef(vector<int>& nums,int left, int right){return nums[rand()%(right-left+1)+left];}int sort(vector<int>& nums,int left, int right, int k){if(left == right) return nums[left];//1.随机选择基准元素int ref = GetRef(nums, left, right);//2.根据基准元素将数组分三块int l = left-1,r = right+1;for(int i = left ; i < r ; ){if(nums[i] < ref) swap(nums[i++],nums[++l]);else if(nums[i] > ref) swap(nums[i],nums[--r]);else i++;}//3.分情况讨论//[left,l][l+1,r-1][r,right]int c = right - r + 1, b = r - l -1;if(c >= k) return sort(nums,r,right,k);else if(b+c >= k) return ref;else return sort(nums,left,l,k-b-c);}int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return sort(nums,0,nums.size()-1,k);}
};

题目分析:这道题的基础依然是上面数组分三块+随机选择基准元素的思想,我们第一次将数组分成三块,[left,l][l+1,r-1][r,right],假设这三个区间的长度分别是a、b、c,然后分情况讨论:

1)c>=k,去[r,right],找第k大

2)b+c>=k,返回ref

3)如果1)和2)不成立,去[l,left],找第k-b-c大        

class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int cnt) {srand(time(nullptr));qsort(nums,0,nums.size()-1,cnt);return {nums.begin(),nums.begin()+cnt};}int GetRef(vector<int>& nums,int left,int right){return nums[rand()%(right-left+1)+left];}void qsort(vector<int>& nums,int left,int right,int cnt){if(left == right) return;int ref = GetRef(nums,left,right);int l = left - 1,r = right + 1,i = left;while(i < r){if(nums[i] < ref) swap(nums[++l],nums[i++]);else if(nums[i] > ref) swap(nums[--r],nums[i]);else i++;}//[left,l][l+1,r-1][r,right]int a = l - left + 1,b = r - 1 - (l + 1) + 1,c = right -r + 1;if(a > cnt) qsort(nums,left,l,cnt);else if(a + b >= cnt) return;else qsort(nums,r,right,cnt - a - b);}
};

题目分析:这道题我们有多种解法,解法1是把这些数放到一个容器中,然后进行排序,时间复杂度是OlogN。解法2是把这些数放到一个大堆里,取堆顶元素,时间复杂度是OlogK。我们这里用第三种解法,快速排序,也是利用数组分三块+随机选择基准元素的思想,在使用这个排序完一遍后,数组被分成了三块,[left,l][l+1,r-1][r,right],假设这几块的区间长度分别为a、b、c:

① a>k,继续在[left,l]中找出最小的元素。

② a+b>=k,直接返回

③ ①和②都不成立,找[right,r]中最小的k-a-b个元素,在加上[left,l]和[l+1,r-1]之间的元素。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

React速成

useRef获取DOM 组件通讯 子传父 function Son({ onGetMsg }){const sonMsg this is son msgreturn (<div>{/* 在子组件中执行父组件传递过来的函数 */}<button onClick{()>onGetMsg(sonMsg)}>send</button></div>) }function App(){const getMsg…

Python基础常见面试题总结

文章目录 1.深拷贝与浅拷贝2.迭代器3.生成器4.装饰器5.进程、线程、协程6.高阶函数7.魔法方法8.python垃圾回收机制 1.深拷贝与浅拷贝 浅拷贝是对地址的拷贝&#xff0c;只拷贝第一层&#xff0c;第一层改变的时候不会改变&#xff0c;内层改变才会改变。深拷贝是对值的拷贝&a…

智能驾驶|迈向智能出行未来,AI如何应用在自动驾驶?

自动驾驶通过人工智能&#xff08;AI&#xff09;、机器学习、传感器融合和实时数据处理&#xff0c;使车辆能够在无需人类干预的情况下自主驾驶。随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;与智能汽车的结合正在成为现代交通运输领域的热潮。无人驾驶…

selenium-Alert类用于操作提示框/确认弹框(4)

之前文章我们提到&#xff0c;在webdriver.WebDriver类有一个switch_to方法&#xff0c;通过switch_to.alert()可以返回Alert对象&#xff0c;而Alert对象主要用于网页中弹出的提示框/确认框/文本输入框的确认或者取消等动作。 Alert介绍 当在页面定位到提示框/确认框/文本录入…

Flythings学习(二)控件相关

文章目录 1 前言2 通用属性2.1 控件ID值2.2 控件位置2.3 背景色2.4 背景图2.5 显示与隐藏2.6 控件状态2.7 蜂鸣器控制 3 文本类TextView4 按键类 Button4.1 系统按键4.2 处理按钮长按事件4.3 处理按键触摸事件 5 复选框CheckBox6 单选组 RadioGroup7 进度条&#xff0c;滑块7.1…

Ubuntu卸载Mysql【ubuntu 24.04/mysql 8.0.39】

一、准备工作 查看ubuntu版本号 查看mysql版本号(如果没有安装mysql,这一步省略) 二、Ubuntu上卸载mysql(如果没有安装mysql这一步省略) 在Ubuntu上卸载MySQL可以通过以下步骤进行&#xff0c;确保完全移除MySQL相关的包和数据&#xff1a; 1. 停止MySQL服务 在卸载之前…

verilog端口使用注意事项

下图存在组合逻辑反馈环&#xff0c;即组合逻辑的输出反馈到输入(赋值的左右2边存在相同的信号)&#xff0c;此种情况会造成系统不稳定。比如在data_in20的情况下&#xff0c;在data_out0 时候&#xff0c;输出的数据会反馈到输入&#xff0c;输入再输出&#xff0c;从而造成不…

java项目之基于vue的工厂车间管理系统的设计源码(springboot+mysql+vue)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的基于vue的工厂车间管理系统的设计。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 基于vu…

QT开发--多线程

第十四章 多线程 QThread 是 Qt 中实现多线程编程的核心类&#xff0c;提供跨平台线程管理。 使用 QThread 有两种方法&#xff1a; 1、 继承 QThread&#xff1a;重写 run() 方法&#xff0c;实现线程的具体操作。Qt4.8 之前较常用。 2、 使用 QObject 和 moveToThread()&…

树莓派应用--AI项目实战篇来啦-17.YOLOv8目标检测-安全帽检测

1. YOLOv8介绍 YOLOv8是Ultralytics公司2023年推出的Yolo系列目标检测算法&#xff0c;可以用于图像分类、物体检测和实例分割等任务。YOLOv8作为YOLO系列算法的最新成员&#xff0c;在损失函数、Anchor机制、样本分配策略等方面进行了全面优化和创新。这些改进不仅提高了模型的…

深入理解Transformer的笔记记录(精简版本)NNLM → Word2Vec

文章的整体介绍顺序为: NNLM → Word2Vec → Seq2Seq → Seq2Seq with Attention → Transformer → Elmo → GPT → BERT 自然语言处理相关任务中要将自然语言交给机器学习中的算法来处理,通常需要将语言数学化,因为计算机机器只认数学符号。向量是人把自然界的东西抽象出…

iOS 14 自定义画中画悬浮窗 Custom AVPictureInPictureController 实现方案

iOS 14&#xff0c;基于 AVPictureInPictureController&#xff0c;实现自定义画中画&#xff0c;涵盖所有功能与难点。 市面上的各种悬浮钟和提词器的原理都是基于此。 Demo源码在文末。 使用 iOS 画中画的要求&#xff1a; 真机&#xff0c;不能使用模拟器&#xff1b;iO…

Android平台RTSP|RTMP播放器PK:VLC for Android还是SmartPlayer?

好多开发者&#xff0c;希望在Android端低延迟的播放RTMP或RTSP流&#xff0c;本文就目前市面上主流2个直播播放框架&#xff0c;做个简单的对比。 VLC for Android VLC for Android 是一款功能强大的多媒体播放器&#xff0c;具有以下特点和功能&#xff1a; 广泛的格式支持…

FFmpeg的简单使用【Windows】--- 简单的视频混合拼接

实现功能 点击【选择文件】按钮在弹出的对话框中选择多个视频&#xff0c;这些视频就是一会将要混剪的视频素材&#xff0c;点击【开始处理】按钮之后就会开始对视频进行处理&#xff0c;处理完毕之后会将处理后的文件路径返回&#xff0c;并在页面展示处理后的视频。 视频所…

MySQL-08.DDL-表结构操作-创建-案例

一.MySQL创建表的方式 1.首先根据需求文档定义出原型字段&#xff0c;即从需求文档中可以直接设计出来的字段 2.再在原型字段的基础上加上一些基础字段&#xff0c;构成整个表结构的设计 我们采用基于图形化界面的方式来创建表结构 二.案例 原型字段 各字段设计如下&…

JAVA就业笔记4——第二阶段(1)

课程须知 A类知识&#xff1a;工作和面试常用&#xff0c;代码必须要手敲&#xff0c;需要掌握。 B类知识&#xff1a;面试会问道&#xff0c;工作不常用&#xff0c;代码不需要手敲&#xff0c;理解能正确表达即可。 C类知识&#xff1a;工作和面试不常用&#xff0c;代码不…

Redis:分布式 - 主从复制

Redis&#xff1a;分布式 - 主从复制 概念配置主从模式info replicationslave-read-onlytcp-nodelay 命令slaveof 主从结构一主一从一主多从 主从复制流程数据同步命令全量同步部分同步实时同步 节点晋升 概念 Redis的最佳应用&#xff0c;还是要在分布式系统中。对于非分布式…

Dockerfile 详解

Dockerfile是自定义Docker镜像的一套规则&#xff0c;由多条指令构成&#xff0c;每条指令都会对应于Docker镜像中的每一层&#xff0c;因为Docker是分层存储的。以下是Dockerfile中各个参数的详解及演示解析&#xff1a; 1. FROM 功能&#xff1a;指定待扩展的父级镜像&#…

【Linux系列】写入文本到文件

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

智慧乡村可视化设计,让美丽的乡村更加魅力。

智慧乡村可视化设计为美丽的乡村注入了新的活力&#xff0c;使其更加魅力四射。 通过可视化设计&#xff0c;乡村的自然风光得以更生动地展现。高清的全景图像、实时的视频监控&#xff0c;让人们仿佛身临其境&#xff0c;感受乡村的青山绿水、田园风光。 古老的村落、宁静的…