【算法】分治-快排

本文主要是介绍【算法】分治-快排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页 ： zxctscl
如有转载请先通知

前言

分治就是分而治之

1. 75. 颜色分类

1.1 分析

就是把数组中的元素分为三块，0全部在左边，1全部在中间，2全部在右边。
这里要用到三个指针，一个i指针用来遍历，一个left用来存放0区域的最后侧，一个用来存放2区域的最左侧。
那么区间就分成了4个

只需要判断nums[i]的值是什么，然后把它放在对应区域。把数组遍历一遍就行，最终i只要等于right就结束遍历，此时中间已经没有要确定区域的数了。

1.2 代码

class Solution {
public:void sortColors(vector<int>& nums) {int left=-1,right=nums.size(),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. 912. 排序数组

2.1 分析

可以先选择一个元素作为基准，把比它小的元素都放在它的左边，把它大的都放在右边，中间放的数就和它相等，这样数组就分为三个区间，递归找一下左边，再递归找一下右边，直到数组全部被排好。

为了减少时间复杂度，选取基准值的时候选取随机数。

2.2 代码

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 k=getRandom(nums,l,r);int i=l,left=l-1,right=r+1;while(i<right){      if(nums[i]<k){swap(nums[++left],nums[i++]);}else if(nums[i]==k)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. 215. 数组中的第K个最大元素

3.1 分析

和上面那题一样，这里也将区间分三块。
随机选取一个基准元素k，根据这个基准元素将区间分三部分，左边都是小于k的，中间都是等于k的，有边都是大于k的。
题目要求找到的是第k大元素，那么在三个区域都有可以，但是如果确定这个第k大元素是在某一个区域的时候，那么剩下的两个区域就都不用考虑。
左边元素个数为a,中间为b，右边为c。
第一种如果在c区域，那么c大于等于k的，因为c区域放的是是大值区域，如果存在第k大的，那么最有可能就在c中，只需要c大于等于k就一定在。
在第二种情况找的时候，就说明第一种情况不存在，在中间的区域，那么就直接返回k就行，因为中间元素都是相等的。
第三种情况，前面两种情况都不存在，那么就在左边区间找，右边区域和中间区域都没有，那么找的就是第k-b-c大的元素。

3.2 代码

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,left=l-1,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,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){int r=rand();return nums[r%(right-left+1)+left];}
};

4. LCR 159. 库存管理 III

4.1 分析

解法一：
可以直接排序，把前面的cnt个数重新放在一个vector表里面返回就行。

解法二：用快速选择算法
就是前面所提到的随机选择基准元素k，把数组分三个区间。

然后统计每一个区间的个数，此时就分为三种情况：
第一种情况：第k小，如果a>k就先从第一个区间找。
第二种情况：a+b大于等于k，那么就直接返回k就行，这个区间值都是相等的。
第三种情况：前面两种情况都不成立，说明这个k在右边这个区域，找k-a-b个元素就可以。

4.2 代码

解法一：

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {sort(stock.begin(),stock.end());vector<int> v;for(int i=0;i<cnt;i++){v.push_back(stock[i]);}return v;}
};

解法二：

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=getRandom(stock,l,r);int i=l,left=l-1,right=r+1;while(i<right){      if(stock[i]<key) swap(stock[++left],stock[i++]);else if(stock[i]==key)i++;else swap(stock[--right],stock[i]);}//分情况讨论int a=left-l+1,b=right-left-1;if(a>k)qsort(stock,l,left,k);else if(a+b>=k) return;else  qsort(stock,right,r,k-a-b); }int getRandom(vector<int>&stock,int left,int right){int r=rand();return stock[r%(right-left+1)+left];}};

有问题请指出，大家一起进步！！！

这篇关于【算法】分治-快排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---