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.

分析：

无

解法1：

class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        // write your code here
        int start = 0, curr = 0, end = nums.length - 1;
        while (curr <= end) {
            if (nums[curr] == 0) {
                int temp = nums[start];
                nums[start] = nums[curr];
                nums[curr] = temp;
                start++;
                curr++;
            } else if (nums[curr] == 1) {
                curr++;
            } else if (nums[curr] == 2) {
                int temp = nums[end];
                nums[end] = nums[curr];
                nums[curr] = temp;
                end--;
            }
        }
    }
}

解法2：

class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        // write your code here
        int zero = 0, one = 0, two = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zero++;
            } else if (nums[i] == 1) {
                one++;
            } else if (nums[i] == 2) {
                two++;
            }
        }

        int i = 0;
        while (i < zero) {
            nums[i] = 0;
            i++;
        }
        while (i < zero + one) {
            nums[i] = 1;
            i++;
        }
        while (i < nums.length) {
            nums[i] = 2;
            i++;
        }
    }
}