移除元素

Leetcode Link: 27. 移除元素 - 力扣（LeetCode）

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解法一

思路：双指针，一前一后，原地交换，slow指针作为边界用来维护所有不是val的数组，fast遍历全部数组，遇到不是val的就和slow互换，slow++；遇到val就++不互换。

题解：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = latter =  0  # 定义两个指针
        while(latter<len(nums)):
            if nums[fast] == val:
                fast += 1
            else:
                nums[fast], nums[slow] = nums[slow], nums[fast]
                fast += 1
                slow += 1
        return slow

解法二

思路：对向双指针 前面的指针用来遍历所有的数字 后面的指针用来保存所有等于val的东西

题解：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        pre = 0  # 头指针
        tail = len(nums)-1  # 尾指针
        while(pre<=tail):
            if nums[pre] == val:
                nums[pre], nums[tail] = nums[tail], nums[pre]
                tail -= 1  # 换过来的没见过，pre不变
            else:
                pre += 1
        return pre

解法三

思路：用内置函数(lists.pop())做，速度变慢了

题解：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        while(1):
            if i >= len(nums):
                break
            if nums[i] == val:
                nums.pop(i) 
            else:
                i += 1  # 不是每次都需要 +1, pop时不需要
        return len(nums)

启发和联系