package com.example.medium;

/**
 * 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.
 * 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?
 * @author FuPing
 *
 */
public class SortColors {
    /**
     * 对值只有0/1/2的数组排序，可以用计数排序，时间复杂度O(n)
     * @param nums
     */
    public void sortColors(int[] nums) {
        int i,sum0 = 0,sum1 = 0;//统计0、1的个数
        for(i = 0;i < nums.length;i++){
            if(nums[i] == 0)sum0++;
            else if(nums[i] == 1)sum1++;
        }
        for(i = 0;i < sum0;i++){
            nums[i] = 0;
        }
        for(;i < sum1 + sum0;i++){
            nums[i] = 1;
        }
        for(;i < nums.length;i++){
            nums[i] = 2;
        }
    }
    /**
     * 对值只有三个范围的数组排序，可以用快速排序，时间复杂度O(n)
     * @param nums
     */
    public void sortColors2(int[] nums) {
        int left = 0,right = nums.length - 1,middle = 0;
        for (int i : nums) {//找到2的元素的个数
                    if(i > 1)middle++;
                }
        middle = right - middle;//1从尾部减去2的个数的位置开始
        while(left <= middle){
            if(nums[right] > 1){//尾部大于1
                right--;
                continue;
            }
            if(nums[middle] == 1){//中间等于1
                middle--;
                continue;
            }
            //此时右边的数必定不是2的数,中间的数必定不是1
            if(nums[left] > 1){//左边大于1
                int temp = nums[right];//和右边交换
                nums[right--] = nums[left];
                nums[left] = temp;
            }else if(nums[left] == 1){//和中间交换
                int temp = nums[middle];
                nums[middle--] = nums[left];
                nums[left] = temp;
            }else{
                left++;
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long startTime = System.currentTimeMillis();
        int nums[] = {2,0};
        new SortColors().sortColors2(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间:"+(endTime-startTime) + "ms");

    }

}