26. 删除排序数组中的重复项

LeetCode

描述：

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

注意

• 在 原地 删除重复出现的元素，表示必须在原数组上操作
• 方法返回的是一个长度，表示过滤后的个数，但并不代表是过滤后的数组长度。

• //给定 nums = [0,0,1,1,1,2,2,3,3,4],
  
  //函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
  
  //你不需要考虑数组中超出新长度后面的元素。

• 为什么返回数值是整数，但输出的答案是数组呢?
  输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

  // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  int len = removeDuplicates(nums);
  
  // 在函数里修改输入数组对于调用者是可见的。
  // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
  for (int i = 0; i < len; i++) {
      print(nums[i]);
  }

  所以，这就是为什么返回的是一个长度，判别结果是一个数组的原因。
  下面这中写法由于没有修改原数组所以错误：

  var removeDuplicates = function (nums) {
      return nums.filter((num, index) => index === nums.indexOf(num)).length;
  };

1.暴力解法逐个删除

• 正向逐位依次和下一位比较，如果相等把当前位删除，因为必须在原数组上操作，所以是使用splice方法。
• 因为使用 splice 方法对元素组删除，所以正向比较时需要注意数组的长度，如果删除了数组项，数组长度需要减1。

 var removeDuplicates = function (nums) {
    var len = nums.length-1,
    i=0;
    for (; i <len; i++) {
        if (nums[i] === nums[i + 1]) {
            nums.splice(i, 1);
            // 因为splice改变了数组的长度，所以数组长度需要减1
            len--;
            // 在删除了数组项之后，下次还需要在当前为比较
            i--
        }
    }
    return nums.length;
};

• 根据上面注释可以换一种写法

var removeDuplicates = function (nums) {
    var len = nums.length-1,
    i=0;
    for (; i <len;) {
        if (nums[i] === nums[i + 1]) {
            nums.splice(i, 1);
            len--;
        }else{
            i++
        }
    }
    return nums.length;
};

• 因为正向遍历需要考虑删除数组项对长度的影响，所以考虑反向遍历。

var removeDuplicates = function (nums) {
    var i = nums.length - 1;
    for (; i > 0; i--) {
        if (nums[i] === nums[i - 1]) {
            nums.splice(i, 1)
        }
    }
    return nums.length;
};

2.双指针

• 注意到最终结果的生成方式，是用返回的数组长度（length）遍历原数组，所以原数组不需要完全是过滤后的结果，只需要前length项是过滤后的结果即可。
• 使用 i , j 两个指针，i指针表示过滤后的数组索引，j表示遍历时的索引
• 如果 nums[i]!==nums[j], j指针向后移动，继续遍历，如果nums[i]===nums[j], i之后向后移动，并且要把nums[j]赋值给nums[i+1];

var removeDuplicates = function (nums) {
    var i = 0,
        j = 1,
        len = nums.length;
    for (; j < len; j++) {
        if (nums[i] !== nums[j]) {
            i++;
            nums[i] = nums[j]
        }
    }
    // 因为i是索引，最后要返回长度所以+1
    return i + 1;
};

打赏