[leetcode刷题]面试经典150题之3删除有序数组中的重复项（简单）

题目 

删除有序数组中的重复项

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

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

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

解决思路：

我们可以通过双指针法来高效解决这个问题：

• 使用两个指针 i 和 j。
• i 是慢指针，指向最后一个处理好的唯一元素的位置。
• j 是快指针，遍历整个数组，寻找与 nums[i] 不同的元素。
• 当 nums[j] 和 nums[i] 不相同时，说明找到了新的唯一元素，将它放到 i+1 的位置，并移动 i。

步骤：

1. 初始化：将 i 初始化为 0，表示当前唯一元素的最后一个位置。j 从 1 开始，遍历整个数组。
2. 比较元素：对于每个 j，如果 nums[j] 和 nums[i] 不同，说明找到新的唯一元素，将其放到 nums[i+1]，并移动 i。
3. 返回结果：最终 i+1 就是去重后数组的长度 k。

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        
        i = 0  # 慢指针，指向唯一元素的最后位置
        for j in range(1, len(nums)):  # 快指针，从第二个元素开始遍历
            if nums[j] != nums[i]:  # 如果找到不同的元素
                i += 1  # 移动慢指针
                nums[i] = nums[j]  # 更新唯一元素
        
        return i + 1  # 返回唯一元素的数量（数组长度）