Cpp Solution O(n) S(1) One pass


  • 0
    R
    void sortColors(int A[], int n) {
    	int pf=-1;
    	int pb =n;
    
    	for(int i=0;i<pb;++i){
    		int t = A[i];
    		//red:0 w:1 b:2
    		while(1!=t){
    			if(0==t){
    				++pf;
    				if(pf<i){
    					int tmp = A[pf];
    					A[pf] = t;
    					t = tmp;
    					A[i] = t;
    					continue;
    				} else {
    					// forword
    					break;
    				}
    			} else if(2==t){
    				--pb;
    				if(pb>i){
    					int tmp = A[pb];
    					A[pb] = t;
    					t = tmp;
    					A[i]=t;
    				} else {
    					break;
    				}
    			}
    		} // end of while
    	} // end of for
    }
    

    the ideal is quite simple, 2 pointers placed at front and back respectively. walk through the array,and switch every found red object( value 0 ) to the front, blue object to back.


Log in to reply
 

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