75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

##Approach 1: two pass

• 第一遍pass：记录0，1，2的个数
• 第二遍pass：重写数组

public class Solution {
    public void sortColors(int[] nums) {
        if(nums == null || nums.length == 0) return;
        int count0 = 0, count1 = 0;
        for(int num : nums) {
            if(num == 0) count0++;
            if(num == 1) count1++;
        }
        for(int i = 0; i < nums.length; i++) {
            if(i < count0) {
                nums[i] = 0;
            } else if(i < count0 + count1) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
}

##Approach 2: one pass 解题思路为slide，维护两个指针。 其中指针0记录的是0的个数，指针1记录的是0和1的总个数。 每次扫描一个num时，移动指针进行overwrite。

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