Sort Colors

题目地址：
https://leetcode.com/problems/sort-colors/#/description

题目：

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.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

解题思路：
这道题是典型的twopointer问题。需要注意的是i的终止条件是<= right。这道题会有一些follow up。比如当array里面存的是element需要用comparator。或者不止3种颜色，而是k种颜色。个人认为当有k种颜色，array长度是n的时候的时间复杂度是O(k * n);

代码：

public void sortColors(int[] nums) {
    if(nums == null || nums.length <= 1){
        return;
    }
    int left = 0;
    int right = nums.length -1;
    for(int i = 0; i <= right; i++){
        int curr = nums[i];
        if(curr == 0){
            swap(nums, i, left);
            left++;
        }
        else if(curr == 2){
            swap(nums, i, right);
            right--;
            i--;
        }
    }
}
private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

public class SortColorObject {
    static class Element implements Comparable<Element>{
        int val;
        public Element(int val){
            this.val = val;
        }


        @Override        public int compareTo(Element o) {
            return this.val - o.val;
        }
    }
    public static void sortColorsObject(Element[] elements) {
        if(elements == null || elements.length <= 1){
            return;
        }
        Element e0 = new Element(0);
        Element e1 = new Element(1);
        Element e2 = new Element(2);
        int left = 0;
        int right = elements.length - 1;
        int i = 0;
//        for(int i = 0; i <= right; i++){//            if(elements[i].compareTo(e1) == 0){//                continue;//            }//            else if(elements[i].compareTo(e0) == 0){//                swap(elements, left++, i);//            }//            else if(elements[i].compareTo(e2) == 0){//                swap(elements, right--, i--);//            }//        }        while(i <= right){
            if(elements[i].compareTo(e0) == 0){
                swap(elements, left, i);
                i++;
                left++;
            }
            else if(elements[i].compareTo(e2) == 0){
                swap(elements, right, i);
                right--;
            }
            else{
                i++;
            }
        }

    }
    private static void swap(Element[] elements, int i, int j){
        Element temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }
    public static void main(String[] args){
        SortColorObject sort = new SortColorObject();

        Element[] elements = new Element[10];
        for(int i = 0; i < 10; i++){
            elements[i] = new Element(i%3);
        }
        for(int i = 0; i < 9; i++){
            System.out.println(i + "'s element is: " + elements[i].val);
        }
        sort.sortColorsObject(elements);
        System.out.println("\nAfter sorting...\n");
        for(int i = 0; i < 9; i++){
            System.out.println(i + "'s element is: " + elements[i].val);
        }
    }
}

public class SortKColors {

    public static void sortColors(int[] nums) {
        if(nums == null || nums.length <= 1){
            return;
        }
        int[] colors = nums;
        int k = 3;
        int pl = 0;
        int pr = colors.length - 1;
        int i = 0;
        int min = 0, max = k;
        while (min < max) {
            while (i <= pr) {
                if (colors[i] == min) {
                    swap(colors, pl, i);
                    i++;
                    pl++;
                } else if (colors[i] == max) {
                    swap(colors, pr, i);
                    pr--;
                } else {
                    i++;
                }
                // printArray(colors);            
            }
            i = pl;
            min++;
            max--;
        }
    }
    private static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void main(String[] args){
        SortKColors sortKColors = new SortKColors();
        int[] nums = new int[10];
        for(int i = 0; i < 9; i++){
            nums[i] = i % 4;
        }
        for(int i = 0; i < 9; i++){
            System.out.println(i + "'s element is: " + nums[i]);
        }
        sortKColors.sortColors(nums);
        System.out.println("\nAfter sorting...\n");
        for(int i = 0; i < 9; i++){
            System.out.println(i + "'s element is: " + nums[i]);
        }
    }
}