[Leetcode] 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.

0 1 2

count-sort like, but in one pass

two pointers start from beginning

1. zero stands for the end of 0s

2. one stands for the end of 1s

3. a third pointer iterate through the array, when found a 1, change the current number to 2 and change one to 1 and move one to next

4. when found a 0, change the current number to 2, change one to 1, move one to next and then change zero to 0, move zero to next (order matters, when one is at the same position as zero, we want this position to be 0 at last, so change it to 1 first,then 0)

    public void sortColors(int[] nums) {
        if(nums == null || nums.length == 0) return;
        int zero = 0;
        int one = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0){
                nums[i] = 2;
                nums[one++] = 1;
                nums[zero++] = 0;
            }
            else if(nums[i] == 1){
                nums[i] = 2;
                nums[one++] = 1;
            }
        }
        
    }

Now we add one restriction: what’s in the array is not integer, is an object, so we could only use swap

if(nums[cur] == 1){
    cur++;
}
else if(nums[cur] == 0){
    swap(cur, zero);
    zero++;
    cur++;
}
else{
    swap(cur, two);
    two--;
}

[Leetcode] Sort Colors

原文：http://www.cnblogs.com/momoco/p/4849076.html