Given a sorted integer array, remove duplicate elements. For each group of elements with the same value do not keep any of them. Do this in-place, using the left side of the original array and and maintain the relative order of the elements of the array. Return the array after deduplication.

Assumptions

• The given array is not null

Examples

• {1, 2, 2, 3, 3, 3} → {1}

Solution: 3指针：slow左侧表示保留元素(exclude slow)，比较fast1与fast2，相同时continue；不同时，如果fast2 - fast1 == 1，说明fast1的元素不重复，则把fast1元素copy到slow++，否则是重复，不对slow处理。同时fast1移到fast2。

退出循环时，有可能fast1还没有复制到slow，所以要额外处理。

  public int[] dedup(int[] array) {
    if (array.length < 2) {
      return array;
    }
    int slow = 0, fast1 = 0;
    for (int fast2 = 1; fast2 < array.length; fast2++) {
      if (array[fast2] == array[fast1]) {
        continue;
      }
      if (fast2 - fast1 == 1) {
        array[slow] = array[fast1];
        slow++;
      }
      fast1 = fast2;
    }

    //fast1 == array.length - 1时，说明fast1元素不重复，并且还没复制到slow。若没有这一步，则少了最后一个元素
    if (fast1 == array.length - 1) {
      array[slow] = array[fast1];
      slow++;
    }
    return Arrays.copyOf(array, slow);
  }

A clever way: