移除一个正序数组中重复的元素


之前翻译过一篇有关 go 切片 的文章,其中介绍了很多有关切片的基础知识。
今天在做了一道 leetcode easy 模式的算法题,题目是“移除一个已排序(正序)数组中所有重复元素,使得每个元素只出现一次,最后返回数组的长度,而且所有的操作都只能在同一个数组上进行”。当然这里的数组对应的就是 go 中的切片。
根据题目要求,这个切片本来就是已经排好序的,所以在进行去重的时候,只需要比较一个第 i 个元素和第 i+1 个元素是否相等即可。只要第 i 个元素和第 i+1 个元素相等,那就直接使用 append() 函数跳过第 i+1 个元素(go 并没有移除切片中某个元素的内建函数)。
我的第一版代码如下:
func ArrayRemoveDuplicates(nums []int) int {
    for i := 0; i < len(nums)-1; i++ {
        if nums[i+1] == nums[i] {
            nums = append(nums[:i], nums[i+1:]...)
        }
    }
}
append(nums[:i], nums[i+1]...) 可以保证当 nums[i] 和 nums[i+1] 相等时,可以从原 nums 切片中删掉 nums[i],如果切片中所有的元素最多重复一次的话,这版代码是可以正常执行的。例如:输入的切片为 [1,1,2,3,5,6,7,7],最终可以输出 6,nums 切片的元素为 [1,2,3,5,6,7]。
但是一旦切片中的元素重复出现了多次的话,程序虽然可以正常执行,但是执行结果是不正确的。例如:输入的切片为 [0,0,1,1,1,2,2,3,3,4],输出为 6,nums 切片的元素为 [0,1,1,2,3,4],可以看到最终生成的切片中仍旧出现了重复的元素。
注:为了方便下面的理解,将 [0,0,1,1,1,2,2,3,3,4] 中的三个 1 元素分别记为 1_11_21_3。,也就是 [0,0,1_1,1_2,1_3,2,2,3,3,4]
原因如下:
当 i=2 时 nums[i]=1_1,i+1=3 时 nums[i+1]=1_2,此时 nums[i] == nums[i+1],然后使用 nums = append(nums[:i], nums[i+1:]...) 跳过 1_1
下一次的循环开始的时候,i=3 满足条件 i < len(nums),程序继续执行,但是此时原切片的元素已经变为 [0,0,1_2,1_3,2,2,3,3,4],所以新的 nums[i]=1_3,可以发现这里的 1_2 被“忽略检测”了。
为了能让程序“重回正轨”,就需要在执行完nums = append(nums[:i], nums[i+1:]...) 之后先让计数器后退一步,也就是 i--,下一次循环再开始的时候,i 的值就会仍为 2,此时 nums[i]=1_2,nums[i+1]=1_3
稍微修改一下的代码:
func ArrayRemoveDuplicates(nums []int) int {
    for i := 0; i < len(nums)-1; i++ {
        if nums[i+1] == nums[i] {
            nums = append(nums[:i], nums[i+1:]...)
            i-- //只修改了这里
        }
    }
}

此博客中的热门博文

pandoc 简单使用

在 GitPage 上部署 Hugo 博客

在 Virtual Box 中安装 Remix OS