Hello大家好!很高兴我们又见面啦!给生活添点passion,开始今天的编程之路!
我的博客:<但凡.
我的专栏:《编程之路》、《数据结构与算法之美》、《题海拾贝》
欢迎点赞,关注!
1、题目
2、题解
我们甚至都不用看题,直接看他那个示例,这不就是升序排序吗?那我们直接用c++自带的sort就行了。但是我们再看看题,人家不让用sort,那咱们自己写个冒泡排序不就完了吗?
代码(一):
class Solution {
public:void sortColors(vector<int>& nums) {int i=0;int j=0;for(i=0;i < nums.size()-1;i++){for(j=0;j<nums.size()-i-1;j++){if(nums[j]>nums[j+1]){int temp;temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}}}
};
没错,这个题就这么简单,通过了。但是咱们还是继续优化一下,毕竟他的复杂度O(n^2)还是不太好看。
我们现在运用一下上一篇的思想,也就是分块数组。这个题出现的数组只有0 1 2,那咱们创建三个变量充当指针,从头遍历数组,如果大于1那就往后放(和后面的交换位置),如果小于1那就往前放。
代码(二):
class Solution {
public:void sortColors(vector<int>& nums) {int i=0;//遍历数组int j=0;int n=nums.size();while(i<n){int temp;if(nums[i]>1){temp=nums[i];nums[i]=nums[--n];nums[n]=temp;//已经减小一次了就别再减了//注意这里不要让i++,因为咱们不知道之前在a[n]那放着的值的大小}else if(nums[i]==1){i++;}else{temp=nums[i];nums[i]=nums[j];nums[j]=temp;i++;j++;}}}
};
注意我们写这个n的时候,我们要保证他先减小再交换。因为如果说我们有个位置还没交换的话,就让n先过去了,到最后i++等于n的时候有可能会出现Bug,由于我们这时候n这个位置还没有被判断过,但是i和n相等就退出循环了,所以部分测试案例过不了。
另外就是以上的交换操作我们可以使用c++自带的swap函数,直接替换掉就可以了。
好了,今天的内容就分享到这,我们下期再见!