0027. 移除元素

0027. 移除元素 #

标签：数组、双指针
难度：简单

题目大意 #

描述：给定一个数组 nums，和一个值 val。

要求：不使用额外数组空间，将数组中所有数值等于 val 值的元素移除掉，并且返回新数组的长度。

说明：

$0 \le nums.length \le 100$。
$0 \le nums[i] \le 50$。
$0 \le val \le 100$。

示例：

示例 1：

1
2
3


输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

1
2
3


输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解题思路 #

思路 1：快慢指针 #

使用两个指针 slow，fast。slow 指向处理好的非 val 值元素数组的尾部，fast 指针指向当前待处理元素。
不断向右移动 fast 指针，每次移动到非 val 值的元素，则将左右指针对应的数交换，交换同时将 slow 右移。
这样就将非 val 值的元素进行前移，slow 指针左边均为处理好的非 val 值元素，而从 slow 指针指向的位置开始， fast 指针左边都为 val 值。
遍历结束之后，则所有 val 值元素都移动到了右侧，且保持了非零数的相对位置。此时 slow 就是新数组的长度。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1
        return slow

思路 1：复杂度分析 #

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。