[LeetCode]Sort Colors

Question
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?

本题难度Medium。

交换法

【复杂度】
时间 O(N) 空间 O(1)

【思路】
有个简单的方法，在follow up已经说了：分别计算出0、1、2的个数，然后对nums重新赋值。不过它要跑两趟（two-pass algorithm）。如何一趟搞定？

我们用三个指针：left、i、right。left是0的边界（left所在的元素可以为0也可以不为0），i为待处理元素，right是2的边界（同理，right所在的元素可以为2也可以不为2）。对于​​num[i]​​的处理：

1. ​​num[i]==1​​，不进行交换，i++
2. ​​num[i]==0​​，swap(left,i)，left++，i++
3. ​​num[i]==2​​，swap(right,i)，right–

简而言之，就是把 0 往前扔，把 2 往后扔即可。

【附】

【注意】
i要从0开始而不能从1开始，否则对于：

nums=[2 1]

会失败。

【代码】

public class Solution {
    public void sortColors(int[] nums) {
        //require
        int size=nums.length;
        int left=0,right=size-1;
        //invariant
        int i=0;
        while(i<=right){
            if(nums[i]==0){
                    swap(left++,i,nums);
                    i++;
            }else if(nums[i]==2){
                swap(right--,i,nums);
            }else{
                i++;
            }
        }

    }
    private void swap(int i,int j,int[] nums){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}