保定网站建设电话,优化seo多少钱,黄海军事最新消息,ps网站导航制作目录
#x1f6a9;了解题意
#x1f6a9;算法分析
第一种方法#xff1a;双指针
#x1f6a9;代码实现一
第二种方法#xff1a;三指针
#x1f6a9;代码实现二 #x1f6a9;了解题意
本题将整数0#xff0c;1#xff0c;2代表红白篮#xff0c;nums中的整数并…
目录
了解题意
算法分析
第一种方法双指针
代码实现一
第二种方法三指针
代码实现二 了解题意
本题将整数012代表红白篮nums中的整数并不是按照红白蓝的顺序排列我们要做的就是让nums中的整数按红白蓝排列比如样例中的nums{202110}最终按照红0白1篮2的顺序排列最终的结果是{001122}。 就是将0红排列在一起1白排列在一起2蓝排列在一起。 算法分析
第一种方法双指针 利用i进行遍历数组ptr来进行划分范围最终得到的结果是 [0,ptr-1] 红色 [ptr,size-1] 白色和蓝色 如果nums[i]0的时候我们就将nums[i]的值和nums[ptr]的值交换然后ptr i遍历完之后我们看到所有的0都再最左边再进行一次遍历但是这时候的i是从ptr开始的
因为上面nums[i]和nums[ptr]交换位置之后ptr所以ptr再下标2的位置。i从下标2开始进行。 如果遇到nums[i]1的时候我们就将nums[i]和nums[ptr]交换位置ptr。 代码实现一
class Solution {
public:void sortColors(vectorint nums) {int n nums.size();int ptr 0;for (int i 0; i n; i) {if (nums[i] 0) {swap(nums[i], nums[ptr]);ptr;}}for (int i ptr; i n; i) {if (nums[i] 1) {swap(nums[i], nums[ptr]);ptr;}}}
};第二种方法三指针 利用i来遍历数组left作为左指针right作为右指针 如果nums[i]0,先让left然后与nums[i]和nums[left]交换位置然后i。 如果nums[i]2,先让--right然后与nums[i]和nums[right]交换位置。
注意这里的i并不往后走因为i是待扫描的区域就是Num[i]是未知的数字我们要继续判断nums[i]是等于多少再进行一次判断。 此时继续判断nums[i]等于多少此时的nums[i]2那么让right先--然后交换nums[i]和nums[right]的值。 如果我们不知道nums[i]的值我们就不能让i.
如果nums[i]1,我们直接就让i 最终的循环判断条件就是 iright即可i与right相遇就结束循环。 代码实现二
class Solution {
public:void sortColors(vectorint nums) {int left-1,rightnums.size();int nnums.size();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]);//此时的i不能因为i对应的值是未扫描的部分}}
}; 关关难过。
