删除有序数组中的重复项 II

题目描述

给你一个有序数组 nums，请你原地删除重复出现的元素，使得每个元素最多只出现两次，返回删除后数组的新长度。

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

返回的数组长度是一个整数，但输出的答案是数组，因为输入数组是通过引用传递的。这意味着在函数内部修改输入数组对于调用者是可见的。

示例 1

输入：nums = [1,1,1,2,2,3]

输出：5, nums = [1,1,2,2,3]

解释：函数应返回新长度 length = 5，并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。不需要考虑数组中超出新长度后面的元素。

示例 2

输入：nums = [0,0,1,1,1,1,2,3,3]

输出：7, nums = [0,0,1,1,2,3,3]

解释：函数应返回新长度 length = 7，并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按升序排列

思路

这个问题要求我们在一个有序数组中删除多余的重复项，使得每个元素最多只出现两次。我们需要在原地完成这一操作，并且不能使用额外的空间。

具体步骤如下：

1. 如果数组长度小于3，直接返回数组长度，因为不会有超过两次的重复项。
2. 使用一个索引 i 记录有效数组的长度，初始化为2，表示前两个元素都是有效的。
3. 从第三个元素开始遍历数组，如果当前元素与 nums[i-2] 不相同，则将当前元素赋值给 nums[i] 并递增 i。
4. 遍历完成后，i 即为新的数组长度。

通过这种方法，我们可以有效地在原地删除有序数组中重复次数超过两次的元素，并返回新的数组长度。

代码

const removeDuplicates = function (nums) {
  const len = nums.length;
  if (len < 3) return len;
  let i = 2; // 记录有效数组的长度，最初有效长度为2
  for (let j = 2; j < len; j++) {
    if (nums[i - 2] !== nums[j]) {
      nums[i] = nums[j];
      i++;
    }
  }
  return i;
};

const arr = [0, 0, 1, 1, 1, 1, 2, 3, 3];
const newLength = removeDuplicates(arr);
console.log(newLength); // 输出新长度
console.log(arr.slice(0, newLength)); // 输出修改后的数组

总结

通过上述方法，我们成功地在原地删除了有序数组中重复次数超过两次的元素。该方法只使用了常数级别的额外空间，时间复杂度为 O(n)，其中 n 是数组的长度。这个方法可以有效地处理题目中的要求，并且在大多数情况下都能表现出色。