算法第二十六天-删除有序数组中的重复项Ⅱ

删除有序数组中的重复项

题目要求

解题思路

题目要求中提到原地修改，那么肯定需要一个指针指向当前即将放置元素的位置，需要另外一个指针向后遍历所有元素，所以[双指针]解法呼之欲出。

• 慢指针slow：指向当前元素放置的位置；则slow-1是刚才已经放置了元素的位置。
• 快指针fast：向后遍历所有元素；

因为最多允许两个重复元素，并且slow-2位置是上上次放置了元素的位置，所以让num[fast]跟num[slow-2]进行比较。每次都是只允许最多两个元素出现重复，这两个元素的位置在slow-1和slow-2

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow=0
        for fast in range(len(nums)):
            if slow<2 or nums[fast] != nums[slow-2]:
                nums[slow]=nums[fast]
                slow +=1
        return slow

1
2
3
4
5
6
7
8
9

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$