删除有序数组中的重复项

发表于 | 分类于 |
字数统计: 631 字 | 阅读时长 ≈ 2 分钟

题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

方法一：双指针

考虑用 2 个指针，一个在前记作 p，一个在后记作 q，算法流程如下：

比较 p 和 q 位置的元素是否相等。

  1. 如果相等，q 后移 1 位

  2. 如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移 1 位
    重复上述过程，直到 q 等于数组长度

返回 p + 1，即为新数组长度。

1.png

优化：

2.png

此时数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。

因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int i = 0;
    for(int j = 1; j < nums.length; j++) {
      if(nums[j] != nums[i]) {
        if(j - i > 1) {
          nums[i + 1] = nums[j];
        }
        i++;
      }
    }
    return i + 1;
  }
}

var removeDuplicates = function(nums) {
  if(!nums.length) return 0;
  let i = 0;
  for(let j = 1; j < nums.length; j++){
    if(nums[j] !== nums[i]){
      if(j - i > 1) {
        nums[i + 1] = nums[j];
      }
      i++;
    }
  }
  return i + 1;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。

  • 空间复杂度：O(1)。只需要使用常数的额外空间。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：40.2 MB, 在所有 Java 提交中击败了58.79%的用户