Another solution, O(n) one pass & O(1) space, without swap, easy understanding


  • 2
    A

    use i, j, k to store where 0, 1, 2 starts

    move one step every time

     void sortColors(int A[], int n) {
                int i=0,j=0,k=0,m;
                bool p0=false,p1=false,p2=false;
                for(m=0;m<n;m++){
                    if(A[m]==0){
                        p0=true;
                        A[i]=0;
                        i++;
                        if(p1) A[j]=1;
                        j++;
                        if(p2) A[k]=2;
                        k++;
                    }else if(A[m]==1){
                        p1=true;
                        A[j]=1;
                        j++;
                        if(p2) A[k]=2;
                        k++;
                    }
                    else {
                        p2=true;
                        A[k]=2;
                        k++;
                    }
                }
            }

  • 0
    E

    not much easy to understand,but is a good solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.