26. 删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
复制代码

解法

双指针 自己的解法，使用while循环，每次拿后面一个数和前面一个数进行比较，如果相等就删除，然后继续比较下一个数。其实自己使用的思想也是双指针的思想。

def removeDuplicates1(nums):

    # 特殊情况判断
    if len(nums) < 2: return len(nums)

    frontNum = nums[0]
    point = 1
    while point < len(nums):
        if frontNum == nums[point]:
            del nums[point]
        else:
            frontNum = nums[point]
            point += 1
    return len(nums)
复制代码

官方解法：

使用快慢指针，没有删除数组，直接赋值在原来数组的位置上。

def removeDuplicates2(nums):

    if not nums:
        return 0

    n = len(nums)
    fast = slow = 1  # 声明快慢指针，初始都指向1，即从第二个数开始比较
    while fast < n:
        if nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]  # 如果快指针指向的数和前一个不同，就将值赋给慢指针指向的数
            slow += 1  # 赋值过后，当前位置就被占了，需要指向下一个位置
        fast += 1  # 遍历一遍过后，快指针指向下一位，比较下一个数
    return slow  # 慢指针的值就是要求的数组的长度
复制代码

复杂度分析

• 时间复杂度：$O(n)$，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
• 空间复杂度：$O(1)$。只需要使用常数的额外空间。

力扣官方答案