此为历史版本和 IPFS 入口查阅区,回到作品页
土豆炒青椒
IPFS 指纹 这是什么

作品指纹

「微软」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 替换套路??
  • ……





CC BY-NC-ND 2.0 授权