刷无敌 27 ～ 删除元素

基本信息

• 题号：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）

测试

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

总结

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