leetcode 80. 删除数组中的重复项2 │ 汪福翔

问题描述

给定一个按非递减顺序排序的整数数组 nums ，删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

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

示例

示例 1

输入: nums = [1,1,1,2,2,3]
输出: 5, nums = [1,1,2,2,3]
解释: 数组中每个元素最多出现两次，所以返回长度为 5，并且前五个元素分别为 1, 1, 2, 2, 和 3。

示例 2

输入: nums = [0,0,1,1,1,1,2,3,3]
输出: 7, nums = [0,0,1,1,2,3,3]
解释: 数组中每个元素最多出现两次，所以返回长度为 7，并且前七个元素分别为 0, 0, 1, 1, 2, 3, 和 3。

解题思路

利用双指针的方法，一个指针用来遍历数组，另一个指针用来标记修改后的数组长度。遍历数组时，如果当前元素和前两个元素都不相等，则将当前元素放到标记位置，然后移动标记位置。遍历完成后，标记位置即为修改后数组的长度。

代码

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }
    idx := 2 // 标记位置
    for i := 2; i < n; i++ {
        if nums[i] != nums[idx-2] {
            nums[idx] = nums[i]
            idx++
        }
    }
    return idx
}

复杂度分析

时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历数组一次。
空间复杂度：O(1)，只需要常数级别的额外空间来存储变量。

#leetcode