当前位置: 首页> 文旅> 旅游 > 大连开发区论坛网_免费咨询猫咪医生_代写文章平台_成都关键词快速排名

大连开发区论坛网_免费咨询猫咪医生_代写文章平台_成都关键词快速排名

时间:2025/7/10 22:23:06来源:https://blog.csdn.net/2401_87995839/article/details/144634464 浏览次数:0次
大连开发区论坛网_免费咨询猫咪医生_代写文章平台_成都关键词快速排名

    Hello大家好!很高兴我们又见面啦!给生活添点passion,开始今天的编程之路!

91bfeb2bb1414a2ebf09cbc4f9706779.gif

我的博客:<但凡.

我的专栏:《编程之路》、《数据结构与算法之美》、《题海拾贝》

欢迎点赞,关注!

1、题目 

ddf0d8ffb326431fb77b49a6c2a55b9a.png

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函数,直接替换掉就可以了。

        好了,今天的内容就分享到这,我们下期再见!

 

 

关键字:大连开发区论坛网_免费咨询猫咪医生_代写文章平台_成都关键词快速排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: