0ms Java 3-way quicksort


  • 2
    L
    public class Solution {
    public void sortColors(int[] nums) {
        int lt = 0, i = 0, gt = nums.length-1;
        while(i<=gt){
            if(nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[lt];
                nums[lt] = tmp;
                i++;
                lt++;
            }
            else if(nums[i] == 1) i++;
            else if(nums[i] == 2) {
                int tmp = nums[i];
                nums[i] = nums[gt];
                nums[gt] = tmp;
                gt--;
            }
        }
    }
    

    }


  • 0
    B

    May you explain why when nums[i] == 2, we don't increment i?


  • 0
    L

    because when nums[i]==2, what we do is exchanging nums[i] and nums[gt]. After the exchange, the new nums[i] has not been checked, so we do not increment i. The reason of decrementing gt is to make sure [gt+1, hi] are all of color 2. Keep in mind in the while loop, [lo,lt-1] are of color 0, [lt, i] are of color 1, [i+1, gt] are unexamined elements, [gt+1, hi] are of color 2.


Log in to reply
 

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