Simple one pass solution


  • 5
    H
    public void sortColors(int[] nums) {
    	int startIndex = 0;
    	int endIndex = nums.length - 1;
    	int temp,i =0;
    	while(i < nums.length) {
    		if (nums[i] == 0 && i != startIndex) {
    			temp = nums[i];
    			nums[i] = nums[startIndex];
    			nums[startIndex++] = temp;
    		} else if (nums[i] == 2 && i < endIndex) {
    			temp = nums[i];
    			nums[i] = nums[endIndex];
    			nums[endIndex--] = temp;
    		} else {
    			i++;
    		}
    	}
    }

  • 0
    H

    Great idea! I have one small optimization for your code: for the condition inside while(), you could use ( i <= end ) instead of ( i < nums.length ) since you always put 2 in the position nums[end], it guarantees all elements starting from index end are 2.


  • 0
    A

    Actually, you don't really need temp since you already knew what nums[i] is.


Log in to reply
 

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