75.颜色分类

自己的思路：

思路和移动零一样，只是进行了两次移动，第一次为”移动2“，第二次为倒着的”移动0“（将0全部移动到最前面），中间自然会剩下1

自己的代码

class Solution {
    public static void sortColors(int[] nums) {
        // ”移动2“
        int i = 0;
        int j = 0;
        while(j < nums.length){
            if(nums[j] != 2){
                nums[i] = nums[j];
                i ++;
            }
            j ++;
        }
        for(;i < nums.length; i ++)
            nums[i] = 2;

        // 倒着移动零
        i = nums.length - 1;
        j = nums.length - 1;
        while(j >= 0){
            if(nums[j] != 0){
                nums[i] = nums[j];
                i --;
            }
            j --;
        }
        for(;i >= 0; i --)
            nums[i] = 0;
    }
}

吴师兄的：三指针

左指针，右指针，中间指针，中间指针遍历，遇到0则和左指针交换，遇到2则和右指针交换（这里要观察一轮，index指针不能马上++）

class Solution {
    public void sortColors(int[] nums) {
        
        // left  指向数组的开始的位置，它指向的位置左侧都是 0
        int left = 0;

        // right  指向数组的结束的位置，它指向的位置右侧都是 2
        int right = nums.length - 1;

        // index 指向数组的开始位置
        int index = 0;

        // index 向后移动，当它越过 right 时跳出循环，不需要再判断了
        // 因为此时说明 index 右侧的都已经是 2
        while( index <= right ){

            // 获取当前的元素值
            int cur = nums[index];
            
            // 如果 index 位置上的元素值为 0
            if(cur == 0){
              // 说明是红色，要放在最前面去
              // 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
              swap(nums,left,index);

              // index 可以向后移动
              index++;

              // left 可以向后移动，它的左侧区域都是 0
              left++;

              // 如果 index 位置上的元素值为 1
            }else if(cur == 1){
                // 说明是白色，就应该放在中间，不用管它，继续移动 index
                index++;

                // 如果 index 位置上的元素值为 2
            }else if(cur == 2){

                // 说明是蓝色，要放在最后面
                // 所以让 index 指向的元素和 right 指向位置上的元素进行交换
                swap(nums,right,index);

                // 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
                // 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
                right--;
            }
        }

    }

    // 通过中间变量，交换两个元素的值
    // nums[i] 的值变为了 nums[j] 的值 
    // nums[j] 的值变为了 nums[i] 的值 
    private void swap(int[] nums, int i ,int j){
        // 使用临时变量 temp，保存 nums[i] 的值
        int temp = nums[i];
        
        // nums[i] 的值修改为 nums[j] 的值
        nums[i] = nums[j];

        // nums[i] 的值修改为 temp 的值
        nums[j] = temp;
    }
}

官方题解：

单指针：其实也是双指针

class Solution {
    public static void sortColors(int[] nums) {
        int i = 0;
        int head = -1;
        int max = nums.length;
        // 移动零
        while(i < max){
            if(nums[i] == 0){
                head ++;
                swap(nums, i, head);

            }
            i ++;
        }
        // 移动1
        i = head + 1;
        while(i < max){
            if(nums[i] == 1){
                swap(nums, i , head+1);
                head ++;
            }
            i ++;
        }
    }

    public static void swap(int[] arrays, int a, int b){
        int temp = arrays[a];
        arrays[a] = arrays[b];
        arrays[b] = temp;
    }
}