题目

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

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

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 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 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

思路

书接上文 删除排序数组中的重复项 的思路，还是双指针的思路，一个指针遍历数组，另一个指针记录当前元素的个数，如果当前元素的个数大于 2，就忽略掉该元素，继续遍历下一个元素，如果当前元素的个数小于等于 2，就将该元素移动到有效数组的末尾，最后返回有效数组的长度。

这里和之前的思路有点不同的地方在于，判断条件上。也就是如何判断当前元素是否应该被移动到有效数组的末尾。如果按照之前的思路来做的话，判断条件应该是 nums[i] != nums[i-1]，但是这里我们需要判断当前元素的个数，所以判断条件还需要加上 count < 2，也就是当前元素的个数小于 2 的时候才移动到有效数组的末尾。但是这样也就意味着需要记录当前元素的个数，如果不记录当前元素的个数的话，也可以直接使用 nums[i] != nums[i-2] 来判断当前元素是否应该被移动到有效数组的末尾，但是这样分析一下会发现，某些情况下会出现错误，因为这里 nums[i-2] 的值可能会随着指针的变动而被替换掉，从而导致判断错误。

比如说 1,1,1,2,2,3 这种情况，如果使用 nums[i] != nums[i-2] 来判断的话，会变成 1,1,2,3，但是实际上应该是 1,1,2,2,3。

要解决这个问题，就需要从头思考判断依据。每次判断 B 指针指向的元素是否有效，其实就是判断该元素的值在有效数组中是否已经出现过 2 次了。而因为整个数组是有序的，所以只需要判断 B 指针的元素和有效数组的倒数第二个元素是否相等就可以了。也就是 nums[B] != nums[A-2]，如果相等的话，就说明该元素已经出现过 2 次了，就不需要移动到有效数组的末尾了。这样就可以避免上面提到的错误了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int) int {
	if len(nums) == 1 {
		return 1
	}

	length := 2
	for i := 2; i < len(nums); i++ {
		if nums[i] != nums[length-2] {
			nums[length] = nums[i]
			length++
		}
	}

	return length
}

代码中 length 的初始值是 2，因为前两个元素是一定有效的，所以默认从第三个元素也就是下标 2 开始遍历和开始替换。这里的判断条件是 nums[i] != nums[length-2]，也就是当前元素和有效数组的倒数第二个元素进行比较，如果相等的话，就说明该元素已经出现过 2 次了，就不需要移动到有效数组的末尾了。否则就将该元素移动到有效数组的末尾。
这里的 length 变量其实就是有效数组的长度，也就是最后返回的值。因为在遍历的过程中，length 变量会随着有效数组的长度而变化，所以最后返回的值就是 length 变量的值。

通用解法

据此就可以总结出删除有序数组中重复元素的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int, k int) int {
	if len(nums) <= k {
		return len(nums)
	}

	length := k
	for i := k; i < len(nums); i++ {
		if nums[i] != nums[length-k] {
			nums[length] = nums[i]
			length++
		}
	}

	return length
}

用 k 来表示允许出现的重复元素的个数，length 变量的初始值是 k，也就是前 k 个元素是一定有效的，所以默认从第 k+1 个元素也就是下标 k 开始遍历和开始替换。
判断条件是 nums[i] != nums[length-k]，也就是当前元素和有效数组的倒数第 k 个元素进行比较，如果相等的话，就说明该元素已经出现过 k 次了，就不需要移动到有效数组的末尾了。否则就将该元素移动到有效数组的末尾。