电商网站开发教学视频,宁夏网络公司排名,赚钱黑渠道入口,古代中国建筑网站个人主页 #xff1a; zxctscl 如有转载请先通知 题目 前言1. 75. 颜色分类1.1 分析1.2 代码 2. 912. 排序数组2.1 分析2.2 代码 3. 215. 数组中的第K个最大元素3.1 分析3.2 代码 4. LCR 159. 库存管理 III4.1 分析4.2 代码 前言
分治就是分而治之
1. 75. 颜色分类 1.1 分析… 个人主页 zxctscl 如有转载请先通知 题目 前言1. 75. 颜色分类1.1 分析1.2 代码 2. 912. 排序数组2.1 分析2.2 代码 3. 215. 数组中的第K个最大元素3.1 分析3.2 代码 4. LCR 159. 库存管理 III4.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(vectorint nums) {int left-1,rightnums.size(),i0;while(iright){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:vectorint sortArray(vectorint nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}void qsort(vectorint nums,int l,int r){if(lr)return;int kgetRandom(nums,l,r);int il,leftl-1,rightr1;while(iright){ 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(vectorint nums,int left,int right){int rrand();return nums[r%(right-left1)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(vectorint nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1,k);}int qsort(vectorint nums, int l, int r,int k){if(lr)return nums[l];int keygetRandom(nums,l,r);int il,leftl-1,rightr1;while(iright){ if(nums[i]key){swap(nums[left],nums[i]);}else if(nums[i]key)i;else{swap(nums[--right],nums[i]);}}//分情况讨论int cr-right1,bright-left-1;if(ck)return qsort(nums,right,r,k);else if(bck)return key;else return qsort(nums,l,left,k-b-c); }int getRandom(vectorint nums,int left,int right){int rrand();return nums[r%(right-left1)left];}
};4. LCR 159. 库存管理 III 4.1 分析
解法一 可以直接排序把前面的cnt个数重新放在一个vector表里面返回就行。
解法二用快速选择算法 就是前面所提到的随机选择基准元素k把数组分三个区间。 然后统计每一个区间的个数此时就分为三种情况 第一种情况第k小如果ak就先从第一个区间找。 第二种情况ab大于等于k那么就直接返回k就行这个区间值都是相等的。 第三种情况前面两种情况都不成立说明这个k在右边这个区域找k-a-b个元素就可以。 4.2 代码
解法一
class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {sort(stock.begin(),stock.end());vectorint v;for(int i0;icnt;i){v.push_back(stock[i]);}return v;}
};解法二
class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1,cnt);return {stock.begin(),stock.begin()cnt};}void qsort(vectorint stock, int l, int r,int k){if(lr)return;int keygetRandom(stock,l,r);int il,leftl-1,rightr1;while(iright){ if(stock[i]key) swap(stock[left],stock[i]);else if(stock[i]key)i;else swap(stock[--right],stock[i]);}//分情况讨论int aleft-l1,bright-left-1;if(ak)qsort(stock,l,left,k);else if(abk) return;else qsort(stock,right,r,k-a-b); }int getRandom(vectorintstock,int left,int right){int rrand();return stock[r%(right-left1)left];}};有问题请指出大家一起进步
