图解双指针 | LeetCode 27. 移除元素

1,533 阅读4分钟

题目描述

原题链接:LeetCode 27. 移除元素

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

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题意解读

划一下题目的重点:

  • 原地移除
  • 不要使用额外的数组空间
  • 不需要考虑数组中超出新长度后面的元素

题目要求我们原地删除所有等于 val 的元素,不能使用额外空间,且不用考虑删除后超出新数组长度后面的元素

也就是说,如果原数组 nums 长度为 x,要删除的 val 元素个数为 y,那么我们只要把这 n 个要删除的元素所在位置用其他有效元素覆盖掉,然后返回最终的数组长度 x - y

题目并非让我们真的删除数组的元素,而是要改写相关元素的值。

思路阐述

那么要如何进行元素的改写呢?

既然要让 val 元素都堆在数组尾部,那么我们就派出一个开拓者探路,只要遇到非 val 元素,就把它覆盖到前面来

因此,我们可以定义两个指针:

  • 快指针 j:用于寻找非 val 元素
  • 慢指针 i:当 j 找到非 val 元素时,就被非 val 元素覆盖

图解思路

以题中的 nums = [3,2,2,3], val = 3 为例。

开始时 ij 都指向下标 0 位置:

初始化时,i = 0, j = 0

此时 j 指向的元素为 val,所以把 j 右移动 1 位:

把快指针 j 右移一位

此时,开拓者 j 找到了一个非 val 元素,那么就赋值给 i 吧:

赋值得到新序列

赋值以后,我们得到了一个新的序列 [2, 2, 2, 3],我们可以得知:

  • j 指向的元素一定不是 val
  • i 指向的元素也一定不是 val,因为它是从 j 指向的元素赋值得来的,j 指向非 val 元素才会进行赋值

这样一来,ij 都完成了本轮使命,继续前进!

因此每次交换以后,我们都同步增长双指针,令 i = i + 1j = j + 1

同步增长双指针

此时 j 又指向了一个非 val 元素,继续赋值:

再一次赋值得到新序列

因为本次 ij 指向元素相同,所以赋值后序列没有改变。赋值操作后,我们继续同步增长双指针:

同步增长双指针

此时 j 指向了一个 val 元素,无法进行赋值操作,继续增长 j,令 j = j + 1

j 超出数组范围

此时我们发现 j 超出数组范围了,循环结束。[2, 2, 2, 3] 即为我们最终所求结果,而红色部分即为新数组长度,长度为 len(nums) - (j - i)

总结一下

设置双指针 ij,其中,j 用于寻找非 val 元素,来覆盖 i 所指向的元素。

  • 初始时:设 i = 0, j = 0
  • 遍历数组:
    • nums[j] != val
      • j 的值赋给 inums[i] = nums[j]
      • 同步增长双指针:i = i + 1, j = j + 1
    • nums[j] == val
      • j 变为快指针:j = j + 1,寻找下一个非 val 元素

具体实现

Python

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        length = len(nums)
        i = 0
        j = 0
        while j < length:
            if nums[j] != val:
                nums[i] = nums[j]
                i = i + 1
                j = j + 1
            else:
                j = j + 1
        res = length - (j - i)
        return res

Golang

func removeElement(nums []int, val int) int {
    length := len(nums)
    if length == 0 {
        return 0
    }

    i := 0
    j := 0
    for j < length {
        if nums[j] == val {
            // 去找一个不是 val 的值
            j++
        } else {
            // 赋值
            nums[i] = nums[j]
            i++ 
            j++
        }
    }

    return length - (j - i)
}

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(1),没有使用到额外空间。

🐱

  • 我的题解项目: github.com/JalanJiang/…
  • 如果你对做题和分享题解感兴趣,欢迎加入 LeetCode 刷题小分队:github.com/leetcode-no…
  • 如果你觉得文章写得不错,欢迎关注公众号「编程拯救世界」,公众号专注于编程基础与服务端研发,定期分享算法与数据结构干货~