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

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

  • 设置三个指针,\(begin=0,end=nums.length,curr=0\),接下来循环时分为三种情况处理:
    • 当\(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--;
        }
   }
}

解法3