找人做仿网站,网站建设管理维护责任书,网站建设购物车,自己创免费网站1. 颜色分类
75. 颜色分类 - 力扣#xff08;LeetCode#xff09; 依据题意#xff0c;我们需要把只包含0、1、2的数组划分为三个部分#xff0c;事实上#xff0c;在我们前面学习过的【算法专题】双指针算法-CSDN博客中#xff0c;有一道题叫做移动零#xff0c;题目要…1. 颜色分类
75. 颜色分类 - 力扣LeetCode 依据题意我们需要把只包含0、1、2的数组划分为三个部分事实上在我们前面学习过的【算法专题】双指针算法-CSDN博客中有一道题叫做移动零题目要求是把0移动到数组的最后端于是我们通过两个指针一个用于遍历数组、另一个用于将数组划分为零区域和非零区域。类似的我们可以通过三个指针一个用于遍历、两个用于将数组划分为三部分即0、1、2。 接下来我们要考虑的是遍历数组时遇到不同的情况如何处理我们可以画一个划分过程中的简单示意图 接下来分析i遍历时会碰到的三种情况 然后就是将算法原理转化为代码建议大家可以拿出纸笔找个例子来模拟一遍这样能对原理有更深的理解也有利于接下来代码的编写。
class Solution {
public:void sortColors(vectorint nums) {int n nums.size();int i 0, left -1, right n;while(i right){if(nums[i] 0) swap(nums[i], nums[left]);else if(nums[i] 1) i;else swap(nums[i], nums[--right]);} }
};
2. 排序数组
912. 排序数组 - 力扣LeetCode 这道题目要求我们将给定数组进行升序排列既然本文标题是快速排序这里当然是用快排来解决啦快排的原理是选择一个基准元素然后让数组中小于等于基准元素的元素都排在基准元素左侧大于基准元素的元素都排在基准元素右侧然后对左侧区间和右侧区间分别做同样的操作体现了分而治之的思想。 不过一般的快排可不能解决这道题因为快排虽然在平均情况下挺高效的但出现相同元素的个数会影响快排的稳定性。 如上图所示在最极端的情况下整个数组都是相同的元素则每次排序只能确定一个元素的位置此时快排的时间复杂读退化到了O(n^2)。而本题的用例正好就出现了许多相同元素的情况所以常规快排是会超出时间限制的我们需要优化过的快速排序。 相信大家都发现了普通快排没有单独考虑相同元素的情况于是会被相同元素影响到效率故而我们可以针对这一点进行优化。单独考虑相同元素的情况后我们将数组划分为三个区域小于基准元素、等于基准元素、大于基准元素。没错实际上这里的划分方式和上一道颜色分类是一样一样的。接下来要做的就是确定基准元素方法有很多不过算法导论中证明了随机选取基准元素的快速排序的效率是最高的因此我们在这里使用随机基准元素。 class Solution {
public:vectorint sortArray(vectorint nums) {srand(time(NULL)); // 种下随机数的种子之后我们就可以通过rand()函数得到随机数了qsort(nums, 0, nums.size() - 1);return nums;}// 值得注意的是本题数据量比较大我们传数组的引用就不需要进行拷贝了能大大减少耗时void qsort(vectorintnums, int l, int r) {if(l r) return;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]);}qsort(nums, l, left);qsort(nums, right, r);}int GetRandom(vectorint nums, int left, int right){int index rand();// 随机数取模区间大小就是偏移量再加上left就得到了随机元素的下标return nums[index % (right - left 1) left]; }
};
