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

Assumptions

• The array is not null

Examples

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

Solution: two pointers

i: [0, i] are processed letters that should be kept （including i）.

j: current index to move. (i, j) is area that we do not care. (j, size - 1]: unknown area to explore

所以每轮j++，符合要求的char(与array[i]比较)，先i++，再复制，否则i不动。返回结果：[0, i]

  public int[] dedup(int[] array) {
    if (array.length < 2) {
      return array;
    }
    int i = 0, j = 1;
    while (j < array.length) {
      if (array[j] != array[i]) {
        i++;
        array[i] = array[j];
      }
      j++;
    }
    return Arrays.copyOf(array, i + 1);
  }

也可以exclude i，此时先i++，再copy j的。返回结果exclude i。与array[i - 1]比较

  public int[] dedup(int[] array) {
    if (array.length < 2) {
      return array;
    }
    int i = 1, j = 1;
    while (j < array.length) {
      if (array[j] != array[i - 1]) {
        array[i] = array[j];
        i++;
      }
      j++;
    }
    return Arrays.copyOf(array, i);
  }