LeetCode 排序数组中删除重复项问题

Question

给定一个按非降序排序的整数数组 nums，就地删除重复项，以便每个唯一元素仅出现一次。元素的相对顺序应保持相同。然后返回 nums 中唯一元素的数量。

考虑 nums 的唯一元素的数量为 k，要获得接受，您需要执行以下操作：

• 更改数组 nums，使 nums 的前 k 个元素按照它们最初在 nums 中出现的顺序包含唯一元素。 nums 的其余元素以及 nums 的大小并不重要。
• 返回k。

在这个问题中，这是我尝试提交的代码，但是

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums = set(nums)
        return len(nums)

为什么这行代码没有被提交。

Python 中的解决方案以及解释为什么这行代码不起作用。

Answer 1

您的代码有错误，因为将列表转换为

set

不会保留原始排序顺序。虽然集合会删除重复项，但它们不会维护元素的顺序，而这是这里所必需的。

更有效的方法是使用两个指针，因为数组是排序的。您可以遍历列表，每当找到唯一元素时，将其移动到列表的前面：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
                
        return k

这使得原始订单在 O(n) 时间和 O(1) 空间中运行，因为它就地修改了数组。