P168 移除有序数组中的重复元素

描述#

这个题目说的是，给你一个有序数组，你要就地（in place）移除数组中的重复元素。然后返回不包含重复元素的子数组长度。

比如说，给你的有序数组是：
[1, 1, 2, 3, 4, 4]
在这个数组中就地移除重复元素后，得到：
[1, 2, 3, 4, _, _]
因此，我们要返回这个子数组的长度 4。
原数组的长度是 6，所以子数组 1,2,3,4 后面实际上还有两个位置。但这两个位置上放什么数字都无所谓。因为根据返回的长度 4，我们就可以确定不包含重复元素的子数组边界。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int p = 1;
    for (int q = 1; q < nums.length; ++q)
      if (nums[q] != nums[q-1])
        nums[p++] = nums[q];
    return p;
  }

}