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

题目连接

https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii

类似题目

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

解题思路

滑动窗口

假设需要删除重复出现的元素, 使得出现次数超过r次的元素只出现r次.

1. 已知数组的前r个元素是一定可以保留的. 试想, 若前r个元素都一样, 则都可以保留; 若前r个元素都不一样, 那更都可以保留了, 所以从第r+1个元素开始遍历
2. 假设有一个窗口, 长度为r, 现在对于每一个新元素, 它是窗口的最后一个元素, 比较它和窗口的第一个元素的值
   • 如果值不同, 说明这个新元素还没有出现超过r次, 可以保留
   • 如果值相同, 说明这个新元素已经出现超过r次, 不可以保留

以r=2为例:

func removeDuplicates(nums []int) int {
	var process func(r int) int
	process = func(r int) int {
		u := 0
		for _, v := range nums {
			if u < r || nums[u-r] != v {
				nums[u] = v
				u++
			}
		}
		return u
	}
	return process(2)
}

• u < r: 表示前面r个元素执行条件语句, 即前r个元素直接保留
• u表示的是当前保留的最后一个元素的下一个元素的index, 即等待被替换的位置
• 若新出现的元素刚好和u-r处的元素不同的话, 那就将其填充到u这个位置

这里的关键点就是u所代表元素的前面的所有元素都已经保留在最终数组里面了.

• 如果新出现的元素和窗口的第一个元素(即u-r指向的元素)相同的话, 说明这个窗口中的所有元素是相同的, 即这个窗口是"饱和"的, 不能再加相同的元素了, 需要等待一个和窗口第一个元素不同的元素
• 如果新出现的元素和窗口的第一个元素(即u-r指向的元素)不同的话, 说明这个窗口还没有"饱和", 可以新的元素添加进来, 保留到最终的数组