删除排序数组中的重复项
2021-03-06 本文已影响0人
追风骚年
先看26 题
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
第一种解法
因为是有序的，所以很简单，弄个变量存储一下前面的值，发现有相同的值，则删除掉
go 里面删除第 i 位的值的写法是 nums = append(nums[:i], nums[i+1:]...)，并且在 i 等于最后 1 位的情况下 nums[i+1:]也不会越界，详细测试过，没有看源码了。
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
last := nums[0]
for i := 1; i < len(nums); i++ {
num := nums[i]
if num == last {
nums = append(nums[:i], nums[i+1:]...)
i--
}
last = num
}
return len(nums)
}
第二种写法
起一个新的数组，新数组都是不重复的数据，后面有一段写回的操作，有点傻逼，整的这么一出。
第二种写法是为第三种写法铺垫
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
newNums := []int{} // 加一个新数组，放入不同德尔值
for _, num := range nums {
// 新数组为空的时候直接加入值就行
// 新数组末尾的值和当前的值是不是相等 如果不相等那也插入新数组
if len(newNums) == 0 || newNums[len(newNums)-1] != num {
newNums = append(newNums, num)
}
}
// 因为 题目要求改变 nums ，所以这里将 newNums 数据回写到 nums 中
for idx, num := range newNums {
nums[idx] = num
}
return len(newNums)
}
第三种写法
如果第二种写法能看懂，第三种也是一样的逻辑，这是我觉得这道题的 BEST 写法。
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
lens := 0 // 假如开了一个新数组，其实没有开，我们只是记录了下新数组的位置
for i := 0; i < len(nums); i++ {
// 新数组为 0 直接向右移动，向右移动表示占有这一段空间
// 新数组最后一个值和 当前值进行比较，如果不相等，则将当前值移动到新数组后面
if lens == 0 || nums[lens-1] != nums[i] {
nums[lens], nums[i] = nums[i], nums[lens]
lens++
}
}
return lens // 直接返回长度即可
}
再来看80题
给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
这道题其实是上面这道题的变种，完全可以用一样的模板
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
lens := 0
for i := 0; i < len(nums); i++ {
if lens <2 || nums[lens-2] != nums[i] {
nums[lens], nums[i] = nums[i], nums[lens]
lens++
}
}
return lens // 直接返回长度即可
}
所以题目是做不尽的，真正掌握其精髓很重要。
