LeetCode中怎样删除排序数组中的重复项

在LeetCode中，删除排序数组中的重复项是一个常见的算法问题。这个问题要求我们在一个已经排序的数组中，删除所有重复的元素，并返回新数组的长度。本文将详细介绍如何解决这个问题，并提供相应的代码示例。

问题描述

给定一个排序数组 nums，你需要原地删除重复出现的元素，使得每个元素只出现一次，并返回新的长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例

输入: nums = [1,1,2]
输出: 2, nums = [1,2]
解释: 函数应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。

解题思路

由于数组是已经排序的，因此重复的元素一定是相邻的。我们可以利用这一特性，通过双指针的方法来解决这个问题。

双指针法

1. 初始化指针：我们使用两个指针 i 和 j，其中 i 是慢指针，j 是快指针。初始时，i 指向数组的第一个元素，j 指向第二个元素。

2. 遍历数组：我们遍历数组，当 nums[j] 与 nums[i] 不相等时，说明 nums[j] 是一个新的元素，我们将 nums[j] 的值赋给 nums[i+1]，然后 i 向前移动一位。

3. 返回结果：遍历结束后，i+1 就是新数组的长度。

代码实现

def removeDuplicates(nums):
    if not nums:
        return 0
    
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    
    return i + 1

代码解释

• 判断数组是否为空：如果数组为空，直接返回 0。
• 初始化指针：i 初始化为 0，j 从 1 开始遍历数组。
• 遍历数组：当 nums[j] 不等于 nums[i] 时，将 nums[j] 的值赋给 nums[i+1]，然后 i 向前移动一位。
• 返回结果：遍历结束后，i+1 就是新数组的长度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

总结

通过双指针法，我们可以高效地删除排序数组中的重复项，并且不需要额外的空间。这种方法不仅适用于LeetCode中的这个问题，也可以应用于其他类似的场景。希望本文能帮助你更好地理解和解决这个问题。