75. Sort Colors ---- M !!

Given an array nums 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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

 

Example 1:

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

Example 2:

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

 

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

A:

----------------下面这个解法，有两个错误的，自己看看，错在哪里？------

public class Solution {
    public void sortColors(int[] A) {
        int pre0 = -1,after2 = A.length;// i is pre
        for(int i = 0;i<A.length;i++){
            if(A[i] ==0){
                pre0++;
                swap(A,pre0,i);
            }else if(A[i] == 2){
                after2--;
                swap(A,i,after2);
                i--;
            }
        }
    }
    private void swap(int [] A, int i,int j){
        A[i] ^= A[j];
        A[j] ^= A[i];
        A[i] ^= A[j];
    }
}

Mistakes:

1: swap这个算法，是不对的。  问题就出自，i，j在flag sort里，有可能是相等的。
2： i<A.length 是不对的, 会导致下标越界

------------------4th pass-----------------

public class Solution {
    public void sortColors(int[] A) {
        int pre0 = -1,after2 = A.length;// i is pre
        for(int i = 0;i<after2;i++){
            if(A[i] ==0){
                pre0++;
                swap(A,pre0,i);
            }else if(A[i] == 2){
                after2--;
                swap(A,i,after2);
                i--;
            }
        }
    }
    private void swap(int [] A, int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

---------下面是用one pass 来做的------利用到了2个pointer------
当runner遇到2 的时候， 和后面交换了之后， 要记得把该runner退一步，重新这个从后面刚switch过来的值。 -------而遇到0 的时候，不用退后。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // i for place 0 lasted filled, and j for lastly fill 2(backward)
        int i = -1, j = nums.size();
        for (int k = 0; k < j; k++) {
            if (nums[k] == 0) {
                swap(nums[++i], nums[k]);
                if (k != i) {
                    k--;
                }
            } else if (nums[k] == 2) {
                swap(nums[--j], nums[k]);
                if (k != j) {
                    k--;
                }
            }
        }
    }
};