题目

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 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 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

思路

之前刚做了删除链表的重复元素，所以拿到这个题就按照之前的思路来做：

1
2
3
4
5
6
7
8
9
10
11
12
func removeDuplicates(nums []int) int {
	for i := 0; i < len(nums)-1; {
		if nums[i] == nums[i+1] {
			nums = append(nums[:i], nums[i+1:]...)
			continue
		}

		i++
	}

	return len(nums)
}

这个是比较简单的思路，就是每次遍历一个元素，判断该元素和下一个元素是否相等，如果相等就删除该元素，直到遍历完所有元素。

当然这个方法其实依赖于切片的删除操作，实际上是比较耗时的，因为每次删除元素都需要移动后面的元素。

双指针

这里的关键优化点是当找到重复元素时，不对后面所有元素进行移动，而是一边遍历，一边将有效元素填充到前面重复元素的位置上。所以考虑使用双指针来降低时间复杂度。

具体来说就是：

  • 用一个指针 A 来记录当前有效元素的下标
  • 用一个指针 B 来遍历整个数组
    • 当 B 指针指向的元素和 B-1 指针指向的元素不相等时，说明 B 指针指向的元素是有效元素，将其放到 A 指针指向的位置上，然后将 A 指针后移一位
    • 当 B 指针指向的元素和 B-1 指针指向的元素相等时，说明 B 指针指向的元素是重复元素，直接跳过
  • 最后返回 A 指针的值即可
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 := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[i-1] {
			nums[length] = nums[i]
			length++
		}
	}

	return length
}

这里 length 和 i 都是从 1 开始的，因为第一个元素是一定有效的，所以默认从第二个元素也就是下标 1 开始遍历和开始替换

另外用 A 指针来记录下一个可替换的位置，然后用 B 指针来遍历整个数组，而决定是否替换的条件就是 B 指针指向的元素和 B-1 指针指向的元素是否相等。就会存在一个疑惑，B-1 指针指向的元素是往前数的，那么其是否会存在该元素被替换的情况呢？ 其实有可能，但不影响。首先来分析 A 指针和 B 指针都是从 1 开始的，所以 B-1 指针指向的元素是从 0 下标的元素，而 A 指针指向的元素是 1 下标的元素。随着快慢指针的移动，B 指针和A 指针的值只会存在两种情况:

  • A 指针指向的元素和 B 指针指向的元素相等：那么 B-1 指针指向的元素就是 A-1 指针指向的元素，也就是当前有效数组的最后一个元素。那么根据算法的逻辑，如果遍历到的元素和当前有效数组的最后一个元素不同，则将该遍历到的元素移动到有效数组的下一个位置上（也就是 A 指针指向的位置）
  • A 指针指向的元素落后于 B 指针指向的元素，那么无论此时 B-1 指针指向的元素是 A 指针指向的元素还是 A 指针后面的元素，该元素都没有被替换过，所以此时按照逻辑去判断 B 指针指向的元素和 B-1 指针指向的元素是否相等即可，如果相等则跳过，如果不相等则将 B 指针指向的元素移动到 A 指针指向的位置上

综上所述，即便 B-1 指针指向的元素是之前被替换过的元素，也不会影响到当前的判断，但是这里仅适用于数组仅保留一个重复元素的情况，如果是保留多个重复元素的情况就不适用了，这放在后面80. 删除排序数组中的重复项 II中继续思考