html企业网站模板,传奇类网页游戏大全,做网站播放未上映的电影,线上教育培训机构十大排名1. 颜色分类
题目链接#xff1a;75. 颜色分类 - 力扣#xff08;LeetCode#xff09;
题目展示#xff1a; 题目分析#xff1a;本题其实就要将数组最终分成3块儿#xff0c;这也是后面快排的优化思路#xff0c;具体大家来看下图。 这里我们上来先定义了3个指针75. 颜色分类 - 力扣LeetCode
题目展示 题目分析本题其实就要将数组最终分成3块儿这也是后面快排的优化思路具体大家来看下图。 这里我们上来先定义了3个指针大家要注意3个指针的作用3个指针在移动的过程中会将数组分成4部分每一部分都有固定的性质3个指针移动的过程中保证指定部分的性质不变就可以实现最终的结果。
当扫描到0的时候我们要保证[0,left]区间全是0那么我们先将left指针向前移动一步然后将该位置的值与i位置的值进行交换然后让i向后移动一步
当扫描到1时要保证[left,i-1]区间全为1那么直接让i即可
当扫描到2时我们要保证[right,n-1]区间全为2那么首先right指针要先往左移动一步然后将该位置的值与i位置的值进行交换这里注意不能让i因为i一旦往后移动待扫描的元素就会被跳过。
代码实现
class Solution {
public:void sortColors(vectorint nums) {int nnums.size();int left-1;int rightn;int 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. 排序数组 - 力扣LeetCode
题目展示 题目分析 这里我们要采用数组分三段的方式来实现快排这是一种比较优秀的方法可以将快排的效率接近于O(NlogN)。
代码实现
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 keygetRandom(nums,l,r);int il;int leftl-1;int rightr1;while(iright){if(nums[i]key){swap(nums[left],nums[i]);}else if(nums[i]key){i;}else{swap(nums[--right],nums[i]);}}//[1,left][left1,right-1][right,r]qsort(nums,l,left);qsort(nums,right,r);}int getRandom(vectorint nums,int left,int right){int r rand();return nums[r%(right-left1)left];}
};
3. 数组中的第K个最大元素
题目链接215. 数组中的第K个最大元素 - 力扣LeetCode
题目展示 题目分析本题其实就是TOP-K问题关于TOP-K问题我们可以使用堆来解决但是使用堆时间复杂度为O(NlogN)本题要求时间复杂度为O(n)我们要利用快速选择算法来解决。 代码实现
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;int leftl-1;int 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;int 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){return nums[rand()%(right-left1)left];}
};
4. 库存管理最小的K个数
题目链接LCR 159. 库存管理 III - 力扣LeetCode
题目展示 题目分析 本题和上一题其实是类似的稍微变化了一下这次我们要返回的是一个数组。 代码实现
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 cnt){if(lr){return;}int keygetrandom(stock,l,r);int il;int leftl-1;int 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;int bright-left-1;if(acnt){return qsort(stock,l,left,cnt);}else if(abcnt){return;}else{return qsort(stock,right,r,cnt-a-b);}}int getrandom(vectorint stock,int left,int right){return stock[rand()%(right-left1)left];}
};
5. 总结
本文为大家介绍了分治专题的其中一部分内容——快排和快速选择这两种算法非常重要需要重点掌握在解题的同时大家要感受分治的思想将大问题转化为小问题然后通过解决小问题最终解决大问题最后希望本文可以为大家带来帮助感谢阅读
