算法题系列6·删除有序数组中的重复项

题目描述

思路分析

实现

题目描述

给你一个 非严格递增排列 的数组 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 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非严格递增 排列

题目来源链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路分析

我们不清楚前面的某元素会和后面到底哪个位置的元素相等，所以势必会有前后多次判断的情况，如果两个指针一块移动，后面再次出现相同的值则前面的已无法回去，而且元素是递增的，因此需要控制前面指针的移动时机，来避免不确定的位置判断、从而产生相等元素但遗漏的情况

办法就是用两个指针，一个快，一个慢，均单方向向前推进，慢的可能在某位置停留多次。

不着急写，先模拟推演一下看应该怎么办。

目的：0,0,1,1,1,2,2 --> 0,1,2,x,x,x,x

把x想象为一个特殊值，用来占位的，占位的只能往后面放，有用的数字在前面依次排列。下面0号位置即索引为0的位置。

由于0和0相等，把第2个0修改为x，即0,x,1,1,1,2,2

循环到了2号位置，此时1号位置发现自己是x，则和下一位的1进行交换，即0,1,x,1,1,2,2

接下来循环到了3号位置，x需要和下一位比较、往后移动，将x和1交换：0,1,1,x,1,2,2 但又发现1号位置和2号位置相等，则把后者改为x：0,1,x,x,1,2,2

循环到了4号位置，发现1号位置的1和4号位置的1又相等，因此4号位置的1被置为x，即：0,1,x,x,x,2,2

循环到了5号位置，由于5号位置的2 > 1号位置的1，因此将2和2号位置的x交换：0,1,2,x,x,x,2

循环到了6号位置，由于6号位置的2 = 2号位置的2，将6号位置修改为x：0,1,2,x,x,x,x

快指针已到头，循环停止。

实现

func removeDuplicates(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	ret, i := n, 0           
	for j := 1; j < n; j++ { 
		if nums[j] <= nums[i] {
			nums[j] = 1e5
			ret--
			continue
		}

		i++
		if nums[i] == 1e5 {
			nums[j], nums[i] = nums[i], nums[j]
		}
	}

	return ret
}

验证：

	var nums1 = []int{1, 1, 2}
	n1 := removeDuplicates(nums1)
	fmt.Println(n1, nums1) // 2 [1 2 100000]

	var nums2 = []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
	n2 := removeDuplicates(nums2)
	fmt.Println(n2, nums2) // 5 [0 1 2 3 4 100000 100000 100000 100000 100000]

	var nums3 = []int{2, 2, 3, 3}
	n3 := removeDuplicates(nums3)
	fmt.Println(n3, nums3) // 2 [2 3 100000 100000]

	var nums4 = []int{0, 0, 1, 1, 1, 2, 2}
	n4 := removeDuplicates(nums4)
	fmt.Println(n4, nums4) // 3 [0 1 2 100000 100000 100000 100000]

	var nums5 = []int{0, 0, 0, 1, 1, 2, 2}
	n5 := removeDuplicates(nums5)
	fmt.Println(n5, nums5) // 3 [0 1 2 100000 100000 100000 100000]

	var nums6 = []int{1, 2, 2, 2, 3}
	n6 := removeDuplicates(nums6)
	fmt.Println(n6, nums6) // 3 [1 2 3 100000 100000]