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

ops/2024/12/22 1:57:37/

一、颜色分类

题目链接:

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);}
};

http://www.ppmy.cn/ops/143907.html

相关文章

MySQL 8.0与PostgreSQL 15.8的性能对比

以下是MySQL 8.0与PostgreSQL 15.8的性能对比&#xff1a; MySQL 8.0性能特点&#xff1a; MySQL在处理大量读操作时表现出色&#xff0c;其存储引擎InnoDB提供了行级锁定和高效的事务处理&#xff0c;适用于并发读取的场景。MySQL通过查询缓存来提高读取性能&#xff0c;查询缓…

子域提取工具,子域名收集神器,支持多种数据源和枚举选项,域名发现工具,可以为任何目标枚举海量的有效子域名,安全侦察工具,利用证书透明原则监控部署的新子域

子域提取工具&#xff0c;子域名收集神器&#xff0c;支持多种数据源和枚举选项&#xff0c;域名发现工具&#xff0c;可以为任何目标枚举海量的有效子域名&#xff0c;安全侦察工具&#xff0c;利用证书透明原则监控部署的新子域。 需要对目标域名的子域进行深入分析&#xff…

C语言中,假如我一个C文件包含了两个头文件,而两个头文件中都有对同一个宏或结构体的定义,编译时如何处理?

两个头文件中都有对同一个宏的定义的情况 在C语言中&#xff0c;如果两个头文件中都定义了同一个宏&#xff0c;并且你在C文件中包含了这两个头文件&#xff0c;会发生宏重新定义的问题。编译器的处理方式取决于宏的具体定义内容&#xff1a; 1. 如果两个宏定义完全相同&…

第十四届蓝桥杯Scratch国赛真题—转动的车轮

转动的车轮 编程实现&#xff1a; 转动的车轮&#xff08;车轮使用画笔绘制&#xff0c;画面中不能出现其他角色&#xff0c;否则0分&#xff09;。 注&#xff1a;角色、背景非源素材。 具体要求&#xff1a; 1). 点击绿旗&#xff0c;背景如图所示&#xff1b; 2). 等待1…

博世智驾新动力:Apache DolphinScheduler如何征服数据处理挑战

视频及PPT等相关资料&#xff1a;点击查看 讲师介绍 陶超权&#xff0c;博世智驾&#xff08;中国&#xff09;后端工程师&#xff0c;负责数据处理和数据调度方面工作&#xff0c;在智能驾驶数据处理领域具有丰富的实践经验。在2024年12月Apache DolphinScheduler社区线上交流…

ffmpeg.exe 命令使用

1. 视频分片&#xff1a;裁剪分割视频成小片段&#xff0c; ffmpeg Documentation Seeking – FFmpeg 1.指定持续时间 使用-t命令。前者要比后者快。 ffmpeg -ss [start] -i [input] -t [duration] -c copy [output] ffmpeg -i [input] -ss [start] -t [duration] -c cop…

安徽移动携手开源网安亮相2024中国国际车联网技术大会,共筑车联网安全新壁垒

近日&#xff0c;由中国通信学会和四川省经济和信息化厅联合主办的2024中国国际车联网技术大会在成都举行。安徽移动联合开源网安推出“基于模糊测试技术的车联网安全检测解决方案”亮相本次大会。该方案已在多家汽车制造商、车载系统开发商落地实践&#xff0c;帮助其深度挖掘…

Vue.js前端框架教程1:Vue应用启动和Vue组件

文章目录 Vue 应用Vue 应用的主要组成部分&#xff1a;启动 Vue 应用&#xff1a; Vue组件基础组件组件注册父子组件组件插槽&#xff08;Slots&#xff09;动态组件和 keep-alive Vue 应用 Vue 应用由几个主要部分组成&#xff0c;每个部分都有其特定的角色和职责。以下是 Vu…