75. 颜色分类

问题

给定一个包含红色、白色和蓝色，一共 $n$ 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 $0、 1 和 2$ 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: $[2,0,2,1,1,0]$
输出: $[0,0,1,1,2,2]$

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗？

解法1（偷懒的办法）

进阶中给出了一种解决方案。两次循环就可以完成。

代码1

java实现

class Solution {
    public void sortColors(int[] nums) {
        if (nums==null || nums.length<2) {
            return;
        }
        //数组中0的数量
        int i=0;
        //数组中1的数量
        int j=0;
        //数组中2的数量不需要计算，因为当i与j都是0时，剩下的肯定都是2
        //开始第一次循环，获取i与j
        for(int n:nums) {
            if (n==0) {
                i++;
            } else if (n==1) {
                j++;
            }
        }
        //开始第二次循环，将0，1，2重新写入数组
        for(int l = 0;l<nums.length;l++) {
            if (i>0) {
                nums[l]=0; 
            } else if (j>0) {
                nums[l] = 1;
            } else {
                nums[l] = 2;
            }
        }
   }
}

解法2

这其实就是荷兰国旗算法。算法如下：

设置三个指针，，接下来循环时分为三种情况处理：
- 当 $nums_{curr} == 0$ 时，交换 $begin$ 与 $curr$ 的值，并且 $begin++;curr++$
- 当 $nums_{curr} == 1$ 时，不做任何处理， $curr++$
- 当 $nums_{curr} == 2$ 时，交换 ${end}$ 与 $curr$ 的值，并且 $end--$

整体算法比较直观，需要注意的一点是，当前值为 $2$ 时， $curr$ 并不往前推进，而是停留在原地。这个的原因在于，如果 $nums_{end}=0$ ,在本次交换后， $nums_{curr}=0$ ，下一轮需要将 $0$ 交换给 $begin$ 。因此，这种情况下 $curr$ 不能往前推进。
还有一个需要注意的地方在于，就是循环的终止条件，如果没有思考清楚，那么很有可能就写成了 $curr<end$ ，但是这种情况是错的。考虑这样一个输入数组 $[2,0,1]$ ,在第一轮的判断时，是走的如上第三种情况，这样 $end$ 在第二轮时就是1了，如果是 $curr<end$ 的判断的话，那么这一步就跳出循环了。最终结果就是 $[1,0,2]$ ，第二个元素并没有参与到比较中来。所以循环的规则应该是 $curr<=end$ 。

代码2

java实现

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        //三个指针的初始化，
        int begin = 0, curr = 0, end = nums.length-1;
        //循环的判断条件见解法中的说明
        while (curr <= end){
            //第一种情况
            if (nums[curr] == 0) {
                nums[curr] = nums[begin];
                nums[begin] = 0;
                curr++;
                begin++;
            } else if (nums[curr] == 1) {
                //第二种情况
                curr++;
            } else {
            nums[curr] = nums[end];
            nums[end] = 2;
            end--;
        }
   }
}