75. 颜色分类 (opens new window)

1.常规解法

需要遍历两次数组。第一次记录每种颜色出现的次数；第二次遍历则根据每种颜色出现的频次重写数组。

class Solution {
    public void sortColors(int[] nums) {
        int red = 0, white = 0, blue = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==0) red++;
            if(nums[i]==1) white++;
            if(nums[i]==2) blue++;
        }
        for (int i = 0; i < nums.length; i++) {
            if (red > 0) {
                nums[i] = 0;
                red--;
                continue;
            }
            if (white > 0) {
                nums[i] = 1;
                white--;
                continue;
            }if (blue > 0) {
                nums[i] = 2;
                blue--;
                continue;
            }
        }
    }
}

2.双指针法

用指针法的核心思路：根据当前的值来实现指针的移动与覆盖。必要时考虑快慢指针的移动次序。

红白快慢指针

仅需要遍历一次。设置红白两种颜色的快慢指针，保证[0,red]之间全是0，(red,white]之间全部都是1。数组遍历的过程中，只需要考虑0和1的情况，每轮循环判断完之后都把当前指针置为2。指针初始化为-1考虑的是当前指针还没有被初始化的情况。

需要注意的是，如果当前指针指向的数为0，那么指向1的快指针移动后，需要考虑覆盖问题：

• 如果当前指针还没有初始化(当前指针扫描时还没出现过1)，那么不需要覆盖
• 如果当前指针已经初始化，则需要初始化。

class Solution {
    public void sortColors(int[] nums) {
       int red = -1, white = -1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==2){
                continue;
            } else if (nums[i] == 1) {
                nums[i] = 2;
                white++;
                nums[white] = 1;
            } else {
                nums[i] = 2;
                white++;
                if (white - 1 >= 0 && nums[white - 1] == 1) {
                    nums[white] = 1;
                }
                red++;
                nums[red] = 0;
            }
        }       
    }
}

红蓝首尾指针

同上面的思路，当前指针扫描时如果遇到0，则往首指针填充；如果扫描到2，则需要往尾指针填充；每次当前指针判断完之后都需要置为1。每次遍历后，尾指针需要移动到非2的位置。

需要注意，如果扫描到2，那么根据尾指针当前要覆盖的位置的值，有以下几种情况：

• 尾指针指向1.则直接覆盖
• 尾指针指向的是0，则尾指针覆盖的同时，首指针也需要进行移动和覆盖。

3.三指针法

直接创建红白蓝三色指针，根据当前指针指向的值，有如下情况：

• 碰到0时，红白蓝三种指针都需要进行移动
• 碰到1时，白蓝指针需要移动
• 碰到2时，只有蓝指针移动

class Solution {
    public void sortColors(int[] nums) {
       int red = 0, white = 0, blue = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==0){
                nums[blue++]=2;
                nums[white++]=1;
                nums[red++]=0;
            } else if (nums[i] == 1) {
                nums[blue++]=2;
                 nums[white++]=1;
                
            } else {
                nums[blue++]=2;
            }
        }
        
    }
}