【算法】分治-快排
个人主页 ： 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];
}
};有问题请指出，大家一起进步！！！