基本信息

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


删除一个数列中指定元素，删除后返回剩余元素的数组。

「⚠️」在空间复杂度 O（1）的情况下完成本题

例如：nums = [3,2,2,3], val = 3
返回 2, nums = [2,2,_,_]

序列删除制定的 3 后，剩下两个 2，空位往后移；返回 2，刚好显示有元素的数组


解题思路

  • 本题如果没有空间复杂度限制，在 O（n）情况下是一道 5 分钟内解答的简单题目，没有任何数据结构和算法基础的小白也能解；
  • 限制空间复杂度为 O（1）后，不能创建额外序列，那当遇到需要删除的元素时，让它与后面的元素进行替换……于是本题演变成了「双指针」问题；
  • 一旦想到了「双指针」本题也就迎刃而解了。


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l, r = 0, len(nums) - 1
        
        # 创建左右双指针后，当左边元素不为要删除的元素，左指针右移 1 位
        # 当左边元素为要删除元素，如果右指针元素也为要删除的元素，右指针向左移；直到右指针为非删除元素时，左右指针互换……
        # 左右指针相遇后，说明完成互换，这时左指针刚好就是我们要返回的值
        while l <= r:
            if nums[l] != val:
                l += 1
            elif nums[r] == val:
                r -= 1
            else:
                # swap
                nums[l], nums[r] = nums[r], nums[l]
                
        return l


Constraints

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50


Big O

  • Time：O（n）
  • Space：O（1）


测试

  • 数列为空时
  • 数列元素全部需要替换时
  • 数列元素混合替换时
  • ……


总结

  • 限制空间复杂度后，需要反应过来可以用「双指针」套路解题
  • 就代码复杂度以及涉及算法高级程度，的确算简单题……