「微软」2022 最后一刷 26 ～ 从排序数组中移除重复元素

基本信息

• 题号：26
• 题厂：微软
• 难度系数：低

已知一个有序·数组，移除数组中的重复元素，返回不重复元素的新数组

1. 只能 in-place 替换，不能使用额外 memory
2. 返回数组的元素和初始数组的顺序一致……

例如 nums = [1,1,2]
返回 2, 我们只要截取数组前两个位即可：nums = [1,2,_]，下划线部分不用管到底是什么元素

解题思路

• 因为已知数组是排序好的，那就遇到不一样的替换。。。。。。
• 要求只能 in-place 替换，引用双指针可以减少代码复杂度。。。。。。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 左右指针都在从 1 开始遍历
        # 如果右指针指向的当前元素和之前元素不一样，那就替换左指针元素为当前右指针指向的元素，同时左指针要前移 1 位
        l = 1
        for r in range(1, len(nums)):
            if nums[r] != nums[r - 1]:
                nums[l] = nums[r]
                l += 1


        return l

lConstraints

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

做题前可以向考官讨论数组有没有为空的情况。。。。。。

测试

• n = 1 时
• 没有重复元素时
• 有重复元素时
• ……

Big O

• 时间复杂度：O（n）
• 空间复杂度：题目限制为 O（1）

总结

• 需要熟悉双指针替换型
• 熟悉 in-place 替换套路？？
• ……