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

【优选算法---分治】快速排序三路划分(颜色分类、快速排序、数组第K大的元素、数组中最小的K个元素)

一、颜色分类

题目链接:

75. 颜色分类 - 力扣(LeetCode)

题目介绍:

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 01 或 2
思路:

这个题目的要求其实就是将0放到最左边,将1放到中间将2放到最后边,思路就是将数组划分为三个部分

设数组大小为 n ,定义三个指针 left, cur, right :
cur 往后扫描的过程中,保证:
  • [0, left)内的元素都是
  • [left , cur - 1] 内的元素都是 1
  • [cur, right] 内的元素是待定元素;
  • (right, n] 内的元素都是 2

当cur遍历到0,交换nums[cur]和nums[left],由于交换前left所指元素一定是1,所以cur和left都可以++。

当cur遍历到1,cur++;

当cur遍历到2,交换nums[cur]和nums[right],right可以--,但是由于交换前right所指元素依旧是待定元素,所以cur不能++,还要判断一下

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

二、快速排序

题目链接:

912. 排序数组 - 力扣(LeetCode)

题目介绍:

给你一个整数数组 nums,请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 104 <= nums[i] <= 5 * 10^4
思路:

与上面的题思路相同,不过我们需要先选择一个基准元素,让这个基准元素左边都是小于他的值,右边都是大于他的值,这样这个基准元素在数组中就排序好了。接下来就是排序左边的区间和右边的区间。

注意,数组中选择的那个基准元素可能存在很多个,一轮排序后 [left,right] 区间都是key,所以这段区间都不需要排序了,只需要排【begin,left-1】和【right+1,end】区间。

假设一个数组全是一样的值,这样三路划分的效率就很块,因为cur就会不断向后遍历,直到碰到right(end),其效率就是O(N)

class Solution {
public:vector<int> sortArray(vector<int>& nums) {qsort(nums,0,nums.size()-1);return nums;}void qsort(vector<int>& nums, int begin, int end) {// 进了这个区间一定能找到if (begin >= end)return;int key = nums[begin];int left = begin;int right = end;int cur = left + 1;// 分成三块while (cur <= right) {if (nums[cur] < key) {swap(nums[left++], nums[cur++]);} else if (nums[cur] == key) {cur++;} else {swap(nums[right--], nums[cur]);}}qsort(nums, begin, left - 1);qsort(nums, right + 1, end);}
};

三、数组的第K个最大元素

题目链接:

215. 数组中的第K个最大元素 - 力扣(LeetCode)

题目介绍:

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 10
思路:

首先我们可以选择一个基准元素,采用三路划分排序一遍,此时 key的位置就排序好了,虽然此时他的左右两边都是无序的,但是此时我们可以判断一下,如果右边的元素个数大于等于k,那说明第k大的元素就在右边,那我们就不用管左边了,如果中间的元素加上右边的元素才大于等于k,那说明第k大的元素就是key,否则我们就到左边找第( k-右边元素数量-中间元素数量)大的元素,这样的算法是非常快的,因为我们不需要将数组完全的排好序。

其次,只要进入到了某个区间找元素,那就说明这值一定在这个区间中,所以当begin>=end时我们就可以返回nums[begin]

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return qsort(nums,0,nums.size()-1,k);}int qsort(vector<int>& nums,int begin,int end,int k){//进了这个区间一定能找到if(begin>=end)return nums[begin];int key=nums[begin];int left=begin;int right=end;int cur=left+1;//分成三块while(cur<=right){if(nums[cur]<key){swap(nums[left++],nums[cur++]);}else if(nums[cur]==key){cur++;}else{swap(nums[right--],nums[cur]);}}int c=end-right;int b=right-left+1;if(c>=k)return qsort(nums,right+1,end,k);else if(b+c>=k)return key;else return qsort(nums,begin,left-1,k-b-c);}
};

四、数组中最小的k个数

题目链接:

LCR 159. 库存管理 III - 力扣(LeetCode)

题目介绍:

仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限

思路:

与上一题的思路一样,我们先选择一个基准元素采用三路划分,将数组分为左中右三部分,如果左边的数量大于等于k,那说明最小的k个数就在左边,就到左边找,中间和右边不管了。如果左边和中间加起来的数量才大于等于k,那就可以直接返回,因为前k个元素已经在左边和中间了,虽然他们不是完全有序的。否则的话,我们就要到右边找最小的(k-a-b)个数了

class Solution {
public:vector<int> inventoryManagement(vector<int>& nums, int k) {qsort(nums,0,nums.size()-1,k);return {nums.begin(),nums.begin()+k};}void qsort(vector<int>& nums,int begin,int end,int k){if(begin>=end) return;int key=nums[begin];int left=begin,right=end;int cur=left+1;//分为三块while(cur<=right){if(nums[cur]<key)swap(nums[left++],nums[cur++]);else if(nums[cur]==key)cur++;elseswap(nums[right--],nums[cur]);}// 判断int a=left-begin;int b=right-left+1;if(a>=k) qsort(nums,begin,left-1,k);else if(a+b>=k) return;else qsort(nums,right+1,end,k-a-b);}
};

相关文章:

【优选算法---分治】快速排序三路划分(颜色分类、快速排序、数组第K大的元素、数组中最小的K个元素)

一、颜色分类 题目链接: 75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; 题目介绍&#xff1a; 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums &#xff0c;原地 对它们进行排序&#xff0c;使得相同颜色的元素相邻&#xff0c;并按照红色、白色、蓝色顺序…...

Spring Cloud OpenFeign

概述 Feign是一个声明式web服务客户端。可以像写接口一样定义http客户端。Feign还支持可插拔的编码器和解码器。Spring Cloud增加了对Spring MVC注释和使用Spring Web中默认使用的HttpMessageConverter的支持。Spring Cloud集成了Ribbon和Eureka&#xff0c;以及Spring Cloud L…...

Oracle 数据库函数的用法(一)

Oracle数据库提供了大量的内置函数&#xff0c;可以用于完成各种操作&#xff0c;如字符串操作&#xff0c;数学计算&#xff0c;日期时间处理&#xff0c;条件判断&#xff0c;序列生成&#xff0c;聚合统计等。以下是一些常用的Oracle数据库函数&#xff1a; 一、oracle 使用…...

【C2C+GRCC】Exploring Disentangled Content Information for Face Forgery Detection

文章目录 Exploring Disentangled Content Information for Face Forgery Detection背景key points研究贡献方法增强解纠缠特性的独立性实验数据内评估跨方法评估跨数据集评估消融实验总结Exploring Disentangled Content Information for Face Forgery Detection 会议/期刊:…...

springboot461学生成绩分析和弱项辅助系统设计(论文+源码)_kaic

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装学生成绩分析和弱项辅助系统软件来发挥其高效地信息处理的作…...

Unity复刻胡闹厨房复盘 模块一 新输入系统订阅链与重绑定

本文仅作学习交流&#xff0c;不做任何商业用途 郑重感谢siki老师的汉化教程与代码猴的免费教程以及搬运烤肉的小伙伴 版本&#xff1a;Unity6 模板&#xff1a;3D 核心 渲染管线&#xff1a;URP ------------------------------…...

使用“NodeMCU”、“红外模块”实现空调控制

项目思路 空调遥控器之所以能够实现对空调的控制&#xff0c;是因为它能够向空调发射出特定的红外信号。从理论上来说&#xff0c;任何能够发射出这种相同红外信号的红外发射器&#xff0c;都可以充当空调遥控器&#xff08;这也正是手机能够控制多种不同品牌空调的原因所在&a…...

2023年西南大学数学建模C题天气预报解题全过程文档及程序

2023年西南大学数学建模 C题 天气预报 原题再现&#xff1a; 天气现象与人类的生产生活、社会经济、军事活动等方方面面都密切相关&#xff0c;大到国家&#xff0c;小到个人&#xff0c;都受到极端天气的影响。2022年6月&#xff0c;全球陆地地区出现了自1850年代末人类有系…...

【大模型】使用DPO技术对大模型Qwen2.5进行微调

前言 定义 DPO&#xff08;Direct Preference Optimization&#xff09;即直接偏好优化算法&#xff0c;是一种在自然语言处理领域&#xff0c;特别是在训练语言模型时使用的优化策略。它的主要目的是使语言模型的输出更符合人类的偏好。 背景和原理 在传统的语言模型训练中&a…...

Maven 生命周期

文章目录 Maven 生命周期- Clean 生命周期- Build 生命周期- Site 生命周期 Maven 生命周期 Maven 有以下三个标准的生命周期&#xff1a; Clean 生命周期&#xff1a; clean&#xff1a;删除目标目录中的编译输出文件。这通常是在构建之前执行的&#xff0c;以确保项目从一个…...

网络不通该如何手动下载torch

如果遇到pip install torch2.5.0 下载不了的情况,大部分是网络的问题.可以考虑下载wheel文件在去安装 查看对应的cuda版本(举个例子:cuda为12.4,找到这个版本的 复制到服务器上下载): 有conda和pip下载的两种方式,二者选其一:如果没有安装anaconda,就直接使用pip的方式下载 如…...

基础电路的学习

1、戴维南定理 ①左边的图可简化为一个电阻&#xff0b;一个电压源。② ③电压源可相当于开路。将R2移到左边&#xff0c;R1和R2相当于并联。RR1//R2 Rx和Rt相等时&#xff0c;灵敏度最大&#xff0c;因此使Rt10K。 104电容是0.1uf。 三位数字的前两位数字为标称容量的有效数…...

对 MYSQL 架构的了解

MySQL 是一种广泛使用的关系型数据库管理系统&#xff0c;其架构主要包括以下几个关键部分&#xff1a; 一、连接层 客户端连接管理&#xff1a;MySQL 服务器可以同时处理多个客户端的连接请求。当客户端应用程序&#xff08;如使用 Java、Python 等语言编写的程序&#xff09;…...

C#中方法参数传值和传引用的情况

对于引用类型 - 传类类型的具体值时 此时传的是引用 - 单纯传类类型 此时传的是个test引用的副本&#xff0c;在方法内修改的是这个副本的指向 传string&#xff0c;集合同理&#xff0c;只要是指向新对象&#xff0c;就是引用副本在指向 对于值类型 - 传普通值类型 …...

获取显示器(主/副屏)友好名称(FriendlyName)

在开发涉及多显示器的应用程序时&#xff0c;获取显示器的友好名称&#xff08;Friendly Name&#xff09;是一个常见需求。本文将深入探讨GetMonitorFriendlyName 方法&#xff0c;了解其实现细节和工作原理。 方法签名 public static string GetMonitorFriendlyName(bool i…...

Apache Solr RCE(CVE-2017-12629)--vulhub

Apache Solr 远程命令执行漏洞&#xff08;CVE-2017-12629&#xff09; Apache Solr 是一个开源的搜索服务器。Solr 使用 Java 语言开发&#xff0c;主要基于 HTTP 和 Apache Lucene 实现。原理大致是文档通过Http利用XML加到一个搜索集合中。查询该集合也是通过 http收到一个…...

2.3 携程的hook实现及dlsym函数

背景知识&#xff1a;&#xff08;排除static 情况&#xff09; 一个进程中可以有相同的命名吗&#xff1f; -- 不能 两个进程之间可以有相同的命名吗&#xff1f;--可以 一个进程和另一个静态库可以有相同的命名吗&#xff1f;--不能 一个进程和另一个动态库之间可以有相同…...

机器学习之KNN算法

K-Nearest Neighbors (KNN) 是一种常见的机器学习算法&#xff0c;广泛应用于分类和回归问题。KNN是一种基于实例的学习方法&#xff0c;它利用训练数据集的实例来进行分类或回归预测。在KNN中&#xff0c;预测的结果依赖于距离度量函数计算出的最近邻实例的标签或值。下面我们…...

《全排列问题》

题目描述 按照字典序输出自然数 11 到 nn 所有不重复的排列&#xff0c;即 nn 的全排列&#xff0c;要求所产生的任一数字序列中不允许出现重复的数字。 输入格式 一个整数 nn。 输出格式 由 1∼n1∼n 组成的所有不重复的数字序列&#xff0c;每行一个序列。 每个数字保留…...

pycharm 快捷键

PyCharm 是一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;提供了丰富的快捷键来提高开发效率。以下是一些常用的 PyCharm 快捷键&#xff08;基于 Windows/Linux 系统&#xff0c;Mac 系统可能略有不同&#xff09;&#xff1a; 通用快捷键 功能快捷键&a…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...