0ms and one-pass solution with c


  • 5
    L
    void sortColors(int* nums, int numsSize)
    {
     int i = 0;
    int red = 0;
    int blue = numsSize - 1;
    while (i <= blue)
    {
    	if (nums[i] == 0)
    	{
    		nums[i] = nums[red];
    		nums[red] = 0;
    		if (i == red)
    			i++;
    		red++;
    	}
    	else if (nums[i] == 2)
    	{
    		nums[i] = nums[blue];
    		nums[blue] = 2;
    		blue--;
    	}
    	else
    	{
    		i++;
    	}
    }
    }

  • 0
    Y

    Hey Lucas,

    Could you please provide explanation (and/or comments) for the above code? That would be very helpful. Thanks!


  • 0
    L

    red is for 0, and blue is for 2;go over the array, when you find a 0, you push it to the 0's zone where "red" indicates its right boundary, and then "red" increases by 1.(by saying push, i mean exchange it with the next element of "red" indicated one); Then you do the similar way to 2s, except that "blue" indicated the left boundary of 2's zone. so, when 0s and 2s are all sorted, 1s must be in the middle. no need for sorting anymore;


  • 0
    C

    nice solution.


Log in to reply
 

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