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

分治算法---快排

一、快排的概念

分治算法--将问题进行分类

1、颜色划分

(1)题目

(2)解题思路

我们可以定义三个指针,一个指针指向0的最后一个位置,一个指针指向2的第一个位置,这样就把他分为了三块,最后一个指针负责遍历数组,如果遇到0就将他移到第一个指针的前面,如果遇到2就把他移到第二个指针的后面

(3)代码书写

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

2、排序数组 

(1)题目

(2) 解题思路

我们找一个key值,依照上题将数组划分为三个部分,大于key,等于key,小于key

key值如何寻找,使用一个随机数,然后将随机数%(right - left +1)+left (这样得到的随机数时间复杂度无限接近于nlogn)

(3)代码书写

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

3、数组中第K个大的数 

(1)题目

 (2)解题思路

我们可以依照上题将数组划分为三个部分(小于key ,等于key,大于key),我们设三个部分的个数分别为a , b , c,因为是第K个大的数如果当k<c的时候我们可以知道第K个大的数一定在第三部分,我们在将第三个部分进行划分,当k<c+b且k>c我们知道第K个大的数一定在第二部分,因为第二部分的值都是等于key的所以,第K个大的数就是K,如果不满足以上的两个情况那么第K个大的数一定在第一部分,我们在将第一部分进行划分.

(3)代码书写

class Solution 
{
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums,0,nums.size()-1,k);}int qsort(vector<int>& nums, int l , int r,int k){if(l == r){return nums[l];}int key = getRandom(nums, l ,r);int i = l;int left = l-1;int right = r + 1;while(i < right){if(nums[i]<key){swap(nums[++left],nums[i++]);}else if(nums[i] == key){i++;}else{swap(nums[--right],nums[i]);}}int c = r - right + 1;int a = left;int b = right - left - 1;if(c >= k){return qsort(nums,right ,r, k);}else if( b+c >= k)return key;else{return qsort(nums,l,left,k - b - c);}}int getRandom(vector<int>& nums, int left ,int right){return nums[ rand() % (right - left + 1) + left];}
};

4、最小的k个数 

1、题目

2、解题思路

同上道题一样,我们首先得到随机值key,将他们分为三部分,设三个部分的长度分为a,b,c. 因为要找前k个小的值,如果a>k,那么值一定在第一部分,我们在将第一部分的划分,如果不满足第一个条件,但是满足a+b>k,那么值一定包含在第一部分和第二部分中,直接返回前k个值(第而部分的 值一样),都不满足,那么值一定包含在第一部分,第二部分和第三部分,我们接着将第三部分的数据进行划分(找前k-a-b个)

3、代码实现

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

 

http://www.lryc.cn/news/583335.html

相关文章:

  • 深度帖:浏览器的事件循环与JS异步
  • Foundry智能合约测试设计流程
  • 【25软考网工】第十章 (3)网络冗余设计、广域网接入技术
  • 【一起来学AI大模型】PyTorch DataLoader 实战指南
  • 前端交互自定义封装类:“双回调自定义信息弹窗”
  • ClickHouse 时间范围查询:精准筛选「本月数据」
  • pytorch 自动微分
  • Git 详解:从概念,常用命令,版本回退到工作流
  • sqlplus表结构查询
  • 3.常⽤控件
  • 跨平台ROS2视觉数据流:服务器运行IsaacSim+Foxglove本地可视化全攻略
  • 【动手学深度学习】4.9. 环境和分布偏移
  • MyBatis之数据操作增删改查基础全解
  • tinyxml2 开源库与 VS2010 结合使用
  • MySQL8.0基于GTID的组复制分布式集群的环境部署
  • 如何通过配置gitee实现Claude Code的版本管理
  • SpringBoot校园疫情防控系统源码
  • Flink1.20.1集成Paimon遇到的问题
  • stm32Cubmax的配置
  • 微信小程序91~100
  • Pycharm 报错 Environment location directory is not empty 如何解决
  • 基于Spring Boot+Vue的巴彦淖尔旅游网站(AI问答、腾讯地图API、WebSocket及时通讯、支付宝沙盒支付)
  • Ragas的Prompt Object
  • NHibernate案例
  • SAP ERP与Oracle EBS对比,两个ERP系统有什么区别?
  • aichat-core简化 LLM 与 MCP 集成的前端核心库(TypeScript)
  • C#项目 在Vue/React前端项目中 使用使用wkeWebBrowser引用并且内部使用iframe网页外链 页面部分白屏
  • Spring IoC 如何实现条件化装配 Bean?
  • HUAWEI HiCar6.0的新变化
  • 一条Redis命令是如何执行的?