个人主页 : zxctscl
如有转载请先通知
题目
- 前言
- 1. 75. 颜色分类
- 1.1 分析
- 1.2 代码
- 2. 912. 排序数组
- 2.1 分析
- 2.2 代码
- 3. 215. 数组中的第K个最大元素
- 3.1 分析
- 3.2 代码
- 4. LCR 159. 库存管理 III
- 4.1 分析
- 4.2 代码
前言
分治就是分而治之
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];}};
有问题请指出,大家一起进步!!!