leetcode 75 颜色分类

一、题目描述

二、解题思路

整体思路

可以采用三指针划分来解决这个问题。本题思路与leetcode283移动零的思路一致。

具体思路

采用三指针的方法来解决，left用于标记全为0的区间的右端点，right用于标记全为2的区间的左端点，i用于遍历向量。

过程模拟

我们借助示例1来模拟三指针划分的过程。

(1)初始化left=-1，right=nums.size()，i=0

(2)此时nums[i]==2,执行swap(nums[--right],nums[i])

注意：此时i不可以加一，因为交换过来的数是未知的

(2)接下来两次nums[i]==0，执行swap(nums[++left],nums[i++])两次

(3)此时nums[i]=2,执行swap(nums[--right],nums[i])

(4)接下来的两次nums[i]=1,执行i++两次

(5)i==right，算法结束

规律总结

(1)初始化三指针，left=-1，right=nums.size(),i=0；

(2)i<right时进行循环：

<1>如果nums[i]==1,i++;

<2>如果nums[i]==0,swap(nums[++left],nums[i++]);

<3>如果nums[i]==2,swap(nums[--right],nums[i])；

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:void sortColors(vector<int>& nums) {//三指针for(int left=-1,right=nums.size(),i=0;i<right;){if(nums[i]==1) i++;else if(nums[i]==0) swap(nums[++left],nums[i++]);else{swap(nums[--right],nums[i]);}}}
};