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

题目描述#

给你一个非严格递增排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

不要使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。

示例 1：

1
输入：nums = [1,1,2]
2
输出：2, nums = [1,2,_]

示例 2：

1
输入：nums = [0,0,1,1,1,2,2,3,3,4]
2
输出：5, nums = [0,1,2,3,4]

解题思路#

核心思想#

快慢双指针：left 指向”下一个不重复元素应写入的位置”，right 扫描数组。因为数组有序，只要 nums[right] 不等于前一个已经固定好的元素 nums[left-1]，就说明遇到了新的不重复值。

算法步骤#

left 从 1 开始（nums[0] 一定保留），right 从 1 遍历到 n-1。
若 nums[right] != nums[left-1]，则说明发现新元素，nums[left] = nums[right] 并 left += 1。
最后返回 left。

关键点：比较对象是 nums[left-1]（已固定区间的最后一个元素），而不是 nums[right-1]，这样即便中间有多个重复也能正确跳过。

逐步举例#

以 nums = [0,0,1,1,1,2,2,3,3,4] 为例：

right	nums[right]	与 nums[left-1] 比较	操作	nums 序列	left
1	0	==0	跳过	[0,0,1,…]	1
2	1	!=0	写 nums[1]=1	[0,1,1,…]	2
3	1	==1	跳过	…	2
4	1	==1	跳过	…	2
5	2	!=1	写 nums[2]=2	[0,1,2,…]	3
6	2	==2	跳过	…	3
7	3	!=2	写 nums[3]=3	[0,1,2,3,…]	4
8	3	==3	跳过	…	4
9	4	!=3	写 nums[4]=4	[0,1,2,3,4]	5

返回 5，前五位 [0,1,2,3,4]，符合预期。

复杂度分析#

时间复杂度：O(n)。
空间复杂度：O(1)。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def removeDuplicates(self, nums: List[int]) -> int:
6
        left = 1
7
        for right in range(1, len(nums)):
8
            if nums[right] != nums[left - 1]:
9
                nums[left] = nums[right]
10
                left += 1
11
        return left

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_basic(self):
12
        nums = [1, 1, 2]
13
        k = Solution().removeDuplicates(nums)
14
        self.assertEqual(k, 2)
15
        self.assertEqual(nums[:k], [1, 2])
16

17
    def test_multi_dup(self):
18
        nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
19
        k = Solution().removeDuplicates(nums)
20
        self.assertEqual(k, 5)
21
        self.assertEqual(nums[:k], [0, 1, 2, 3, 4])
22

23
    def test_no_dup(self):
24
        nums = [1, 2, 3, 4]
25
        k = Solution().removeDuplicates(nums)
26
        self.assertEqual(k, 4)
27

28
    def test_single(self):
29
        nums = [5]
30
        k = Solution().removeDuplicates(nums)
31
        self.assertEqual(k, 1)
32

33

34
if __name__ == "__main__":
35
    unittest.main()