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

easy

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

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

原地删除

append 函数看起来蛮耗时的。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// removeDuplicates 比较蠢的 一次遍历
func removeDuplicates(nums []int) int {
	dupLen := 0
	oriLen := len(nums)
	for i := 0; i < len(nums)-1; {
		if nums[i] == nums[i+1] {
			nums = append(nums[:i+1], nums[i+2:]...) // 删除 i+1
			dupLen++
			// 此处不执行 i++
		} else {
			i++
		}

	}
	return oriLen - dupLen
}

双指针（重复元素后移）

一个指针 i 进行数组遍历，另外一个指针 j 指向有效数组的最后一个位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// removeDuplicates 把重复的元素移到最后面 （其实是覆盖掉）
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	i, j := 0, 0
	for i < len(nums)-1 {
		for nums[j] == nums[i] {
			// 右移j至与i不同处
			j++
			if j == len(nums) {
				return i + 1
			}
		}
		nums[i+1] = nums[j] // 覆盖 跟替换一个意思
		i++
	}
	return i + 1
}