Another space O(1) method based on partition


  • 0
    G
    class Solution {
    public:
    	void sortColors(int A[], int n) {
    	    int l=0, r=n-1;
    	    while (l<=r) {
    	        while (l<=r && !A[l])
    	            l++;
    	        if (l<r)
    	            A[l]^=A[r], A[r]^=A[l], A[l]^=A[r];
    	        while (l<=r && A[r])
    	            r--;
    	        if (l<r)
    	            A[l]^=A[r], A[r]^=A[l], A[l]^=A[r];
    	    }
    	    r=n-1;
    	    while (l<=r) {
    	        while (l<=r && A[l]==1)
    	            l++;
    	        if (l<r)
    	            A[l]^=A[r], A[r]^=A[l], A[l]^=A[r];
    	        while (l<=r && A[r]==2)
    	            r--;
    	        if (l<r)
    	            A[l]^=A[r], A[r]^=A[l], A[l]^=A[r];
    	    }
    	}
    };

Log in to reply
 

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