leetcode 75.颜色分类（详解）数组分块c++

题目链接：75. 颜色分类 - 力扣（LeetCode）

1.题目分析

• 这道题和上一题的移动零有点像leetcode 283. 移动零（详解）双指针c++-CSDN博客，移动零是把一个数组分成两块，这道题是把一个数组分成3块，其中分配标准可以是0、1、2区域，也可以是左边小于1，中间等于0，右边大于1 

2.算法原理

数组分块-数组分三块-荷兰国旗问题
解法：三指针
定义三个指针:

• i:扫描数组
• left:标记的就是 0 区间的最后一个元素
• right:标记的就是 2 区间的第一个元素

扫描过程中会分成四个区域，扫描完后是三个区域，如上图；当 i 扫描到2的时候，我们是想要2放到2区间，只需要让在right-1这个位置的元素和2交换一下，再让right向左移动一位，就把2放到2区间了，注意现在 i 还不能动，因为交换过来的数，还要对它再进行判断；扫描到0，要把0放到0区间，可以让它和left+1位置的元素交换，再让left+1，就把0放到0区域了；扫描到1，要把1放到1区间，i 向右移动一位，就自动进入到1区间了；i与right相遇的时候停止，时间复杂度是O(N)

分类讨论nums[i]：

• 2：swap( right - 1, i )，right - -;
• 0：swap( left + 1, i )，left++，i++;       
• 1：i++;  

代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
            int left = -1, i = 0, right = nums.size();
            
            while(i < right)
            {
                if (nums[i] == 0) swap(nums[i++], nums[++left]); //交换left+1位置
                else if (nums[i] == 2) swap (nums[i], nums[--right]); //交换right-1位置,i要继续判断，所以不动
                else ++i;
            }
        }
};