问题

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn’t matter what values are set beyond the returned length.

  • Level: Hard

解题思路

如果没有O(1)的空间复杂度，并且不关注修改后原来数组的结果。我们可以利用set或者map来解决此题。现在题目既然要求O(1)的空间复杂度解决，那么可以使用“双指针”的思路和排序数组的特性来解决此题,具体思路如下：

  1. 设pos为新数组下标值，初始化为0；idx为原数组的下标，[1, n);
  2. 若arr[pos] != arr[i],则 arr[pos++] = arr[i]
  3. 重复2，直到 i = n;
  4. 返回 新数组的长度：pos+1

详细代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeDuplicates(int[] nums) {
    if (null == nums || nums.length <= 0) {
        return 0;
    }
    int len = nums.length;
    int pos = 0;
    for (int idx = 1; idx < len; ++idx) {
        if (nums[pos] != nums[idx]) {
            nums[++pos] = nums[idx];
        }
    }
    return pos + 1;
}
  • 时间复杂度为O(n),其中n为排序数组的长度；
  • 空间复杂度为O(1)