删除排序数组中的重复项

Posted on Edited on In Word count in article: 594 Reading time ≈ 1 mins.
给定排序数组，原地删除重复元素

问题

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

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

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

方法

首先注意数组是有序的，那么重复的元素一定会相邻。

要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。

考虑用 2 个指针，一个在前记作a，一个在后记作 b，算法流程如下：

比较 a 和 b 位置的元素是否相等。

如果相等，b 后移 1 位
如果不相等，将 a 位置的元素复制到 a+1 位置上，a 后移一位，b 后移 1 位
重复上述过程，直到 b 等于数组长度。

返回 a + 1，即为新数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    a, b := 0, 1
    for ;b < len(nums);b++ {
        if b == len(nums) {
            break
        }
        if nums[b]!=nums[a] {
            nums[a+1] = nums[b]
            a++
        }
    }
    return a+1
}