一、编程题：75. 颜色分类（双指针，循环不变量）

1.题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。 LeetCode题目链接。

2.示例1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

3.示例2：

输入：nums = [2,0,1]
输出：[0,1,2]。

4.提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

5.进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗

二、解题思路

1.思路

解决方法1（个人想法）：

• Step1.创建三个变量用于存储0，1，2出现的个数；
• Step2.用for循环遍历数组，计算出0，1，2出现的个数；
• Step3.再用for循环根据0，1，2出现的个数对数组进行重写即可；

解决方法2（双指针，循环不变量）：官方视频讲解

• Step1.定义循环不变量，
           all in [0, left) == 0
           all in [left, i) == 1
           all in (right, len - 1] == 2

• Step2.创建两个指针left，right，其中left=0，right=nums.length-1，left指针用于指向最左边的位置，rigtht指针指向最右边的位置；

• Step3.当nums[i] == 0时，则与最右边的位置left进行交换，交换之后则left要自加1，并且i自加1（这里用for循环进行遍历时，i不用考虑自加）；

• Step4.当nums[i] == 2时，则与最左边的位置right进行交换，交换之后right要自减1，并保持i不变（这里用for循环时，i要自减1）；

• Step5. 用for实现该双指针时，不需要考虑Step5。 当nums[i] == 1时，不做处理，让循环i自加1即可；

三、代码实现

。每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一：

class Solution {
    public void sortColors(int[] nums) {
        //第一种方法（分组）
        int zero = 0, one = 0, two = 0;
        for(int right = 0; right < nums.length; right++){
            switch(nums[right]){
                case 0: zero++;break;
                case 1: one++;break;
                case 2: two++;break;
            }
        }
        // System.out.println("zero="+zero+" one="+one+" two="+two);
        for(int right = 0; right < nums.length; right++){
            if(zero > 0){
                nums[right] = 0; zero--;
            }else if(one > 0){
                nums[right] = 1; one--;
            }else if(two > 0){
                nums[right] = 2; two--;
            }
        }
    }
}

解法二：

• for循环实现

class Solution {
    public void sortColors(int[] nums) {
        //第二种方法（双指针）
        // 循环不变量
        // all in [0, p0) == 0 红
        // all in [p0, i) == 1 白
        // all in (p2, len - 1] == 2 蓝
        // 把红色和蓝色放在两边，中间自然就是白色
        int left = 0, right = nums.length - 1;
        //for循环实现
        for(int i = 0; i < right+1; i++){
            switch(nums[i]){
                case 0:
                    swap(nums, left++, i);
                    break;
                case 2:
                    //当值为2时，则进行交换，并把right指针自减1并保持i不变
                    swap(nums, i--, right--);
                    break;
            }
        }
    }
    public void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

• while循环实现

class Solution {
    public void sortColors(int[] nums) {
        //第二种方法（双指针）
        // 循环不变量
        // all in [0, p0) == 0 红
        // all in [p0, i) == 1 白
        // all in (p2, len - 1] == 2 蓝
        // 把红色和蓝色放在两边，中间自然就是白色
        int left = 0, right = nums.length - 1;
        //while循环实现
        int i = 0;
        while(i <= right){
            switch(nums[i]){
                case 0:
                    swap(nums, left++, i++);
                    break;
                case 1:
                    i++;
                    break;
                case 2:
                    swap(nums, i, right--);
                    break;
            }
        }
    }

    public void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

提交结果：

总结

以上就是今天要讲的内容，一开始做题的时候，首先想到就是用for循环遍历计数，然后再用for循环重写原数组，后面看了官方视频讲解之后，接触到一个新概念：循环不变量，根据循环不变量以及双指针思想在对该题进行理解，对双指针思想的印象很深刻，所以就赶紧记录一下这个方法，开阔一下思路。