sort-colors

1.jpg 2.jpg

荷兰国旗问题

//双指针，red和blue从两边往中间走
class Solution {
public:
    void sortColors(int A[], int n) {
        int red=0,blue=n-1;
        int cur=0;
        while(cur<=blue)
        {
            if(A[cur]==0)swap(A[cur++],A[red++]);
            else if(A[cur]==2)swap(A[cur],A[blue--]);
            else cur++;
        }
    }
};


class Solution {
public:
    void sortColors(int A[], int n) {
        int red=0,blue=n-1;
        for(int i=0;i<blue+1;)
        {
            if(A[i]==0)swap(A[i++],A[red++]);
            else if(A[i]==2)swap(A[i],A[blue--]);
            else i++;
        }
    }
};