75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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 a one-pass algorithm using only constant space?

要求我们只用一次遍历就得出结果。参考了来offer的教程 https://www.youtube.com/watch?v=yTwW8WiGrKw&list=PLTNkreZiUTIL-S_VJBLRxlmGktAQtla-m&index=3

采用了三个挡板来分割四种类型的字母（数字）——0，1，xxx（未确定），2

　类似于　000 | 11| xxx | 22

　　　　0——[0,i)

　　　　1——[i,j)

　　　　x——[j,k]

　　　　2——(k,length-1]

然后用设index i，j，k分别代表0的末位，未知数字的首位和2的首位。初始值为i=0, j=0, k=length-1;

这样，用一次遍历，检查 nums[ j ]的值，是0就和 nums[ i ]交换位置，同时 i++，j++。

是1就 j++。

是2就和nums[ k ]交换位置，同时k--。

代码如下

class Solution {
    public void sortColors(int[] nums) {
        if(nums.length <=1 || nums == null) return;
        int i = 0, j = 0, k = nums.length -1;
        while(j<=k){
            if(nums[j]==0){
                swap(i++,j++,nums);
            }
            else if(nums[j] == 1){
               j++; 
            }
            else if(nums[j] == 2){
                swap(j,k--,nums);
            }
        }
    }
    public void swap(int i, int j, int nums[]){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

https://leetcode.com/problems/sort-colors/discuss/26472/Share-my-at-most-two-pass-constant-space-10-line-solution

low-high two pointers.