75. Sort Colors

荷兰国旗问题，同快排三路解法，不过lt是从0开始，因为pivot不是第一个元素。时间复杂度O(n)

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

public void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

不交换，但是会赋值很多次的解法，[0,i)区间为0，[i,j)区间为1，[j,n)区间为2。

public void sortColors(int[] nums) {
    int i = 0, j = 0;
    for (int n = 0; n < nums.length; n++) {
        int pivot = nums[n];
        nums[n] = 2;
        if (pivot < 2) {
            nums[j] = 1;
            j += 1;
        } 
        if (pivot == 0) {
            nums[i] = 0;
            i += 1;
        }
    }
}