75. Sort Colors

• 75. Sort Colors
  • Description
  • Intuition
    • Starting 0
    • Starting 1
    • Starting 2
  • Pitfall
  • Solution
  • Reference](#reference)
    • Starting 1
    • Starting 2
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

这题这样做，假设分类0, 1, 2，我们将使用三个指针

• notZero: 永远指向第一个不是0的数字
• notOne: 永远指向第一个不是1的数字
• notTwo: 永远指向第一个不是2的数字

procedure three-way-partition(A : array of values, mid : value):
    i ← 0
    j ← 0
    n ← size of A - 1

    while j ≤ n:
        if A[j] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[j] > mid:
            swap A[j] and A[n]
            n ← n - 1
        else:
            j ← j + 1

Starting 0

swap notZero and notOne

notZero moves, notOne moves

Starting 1

notOne moves

Starting 2

swap with notOne and notTwo

notTwo moves

此时不可以move notOne，交换过去的可以是0，也可以是1

Pitfall

Solution

  public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) {
      return;
    }
    int firstNotZero = 0, firstNotSecond = nums.length - 1;
    // 需要使用等于号，因为i并未经过firstNotSecond, <tt>firstNotSecond</tt>
    for (int i = 0; i <= firstNotSecond; ) {
      if (nums[i] == 0) {
        swap(nums, i, firstNotZero);
        i++;
        firstNotZero++;
      } else if (nums[i] == 1) {
        i++;
      } else {
        // this is a swapping number [0, 1] to position i
        swap(nums, i, firstNotSecond);
        firstNotSecond--;
      }
    }
  }

  private static void swap(final int[] nums, final int i, final int j) {
    final int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

Reference

• Wikipedia
• CSDN Blog
• Leetcode Discussion-1-pass-in-place-solution-with-explanation)
• Share my at most two-pass constant space 10-line solution