【刷题笔记2】删除有序数组中的重复项

题目来源LeetCode 26.删除有序数组中的重复项
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

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

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

二、提示

• $0\le nums.length\le 3\ast 10^4$
• $-10^4<=nums[i]<=10^4$
• $nums$已按升序排列

三、思考

• 注意边界，长度为0或1直接输出
• 有序数组
• 原地修改，O(1)的空间复杂度
• 删除重复元素
• 返回的是删除后的长度

四、解法（快慢双指针）

从小案例入手：

l1 = [2,4,5,6,6,8]

l2 = [2,2,3,4,5,5,9,9]

l3 = [2,2,2,3,3,5,7,7,9]

• 需要比较，意味着两个指针；原地修改意味着移动

• 慢指针i从0遍历数组，快指针j从1遍历数组

  • 慢指针用于判断交换的左边位置和重复值比较
  • 快指针用于判断交换的右边位置和重复值比较

• 当慢指针指向值与快指针指向值不相等时，慢指针+1，快指针的值与慢指针指互换

• 快指针向后移动，直到移动到len(nums)

• 返回慢指针的下标+1

• 实际上是快指针走完就结束，时间复杂度是$O(n)$

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        i, j = 0, 1
        while j < len(nums):
            if nums[j] != nums[j - 1]:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i + 1