leetcode-27

date
‣
slug
leetcode-27
status
Published
tags
Leetcode
summary
type
Post

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解析

先来分享一下题目要求
  • 通过 原地修改数组 移除所给值
  • 元素顺序可改变
  • 返回数组长度 注：其实数组也是会被判定的，因为传入的是数组的引用

第一解

func removeElement(nums []int, val int) int {
    for i:=0; i<len(nums); i++{
        if nums[i] == val{
            nums = append(nums[:i], nums[i+1:]...)
        }
    }
    return len(nums)
}
第一次写下了这个解法，遍历数组，如果是需要移除的数，就移除，最后返回数组长度
毫无疑问，这是个错解
因为没有考虑移除元素后，指针i已经+1，导致漏过了中间的元素

第二解

func removeElement(nums []int, val int) int {
    j := 0
    for i:=0; i<len(nums); i++{
        if nums[i] != val{
            nums[j] = nums[i]
            j++
        }
    }
    return j
}
仔细阅读题目后，发现上一题还犯了一个错误：没有原地修改数组
因为其实使用 append 的过程中，是利用了 go 中 slice 的特性，创建了两个新数组然后合并
那么，如果要原地修改数组的话，无疑是一个提示： 双指针
这里定义两个指针 i, j 用快指针 i 来遍历数组
若得到的值并不是所给的需要移除的值，就将 i 处的元素放至 j 处，然后让慢指针 j 自增 1
核心思想就在于 指针j 其实是在创建答案所需的数组，只不过是覆盖原有元素来实现的
那么当 指针i 遍历了整个数组后， 不需要删除的元素已经随着 指针j 创建好了， 而 j 正是数组的长度， 将其返回即可

第三解

LeetCode 官方还给出了另一种方法，考虑数组[1,2,3,3] 要移除的元素1
因为移除的元素很少，但上面一个正解仍旧需要复制所有的非移除元素
第三解解决了这个问题
通过遍历数组，将最后一个元素放到当前需要元素上（效果等同于数组长度-1） 那么就能减少不需要移除的元素的复制
    func removeElement(nums []int, val int) int {
    i := 0
    j := len(nums)
    for i < j {
        if nums[i] == val {
            nums[i] == nums[j-1]
            j--
        } else {
            i++
        }
    }
    return j
}

总结

  • 类似原地修改数组的题目，都可以考虑用双指针法
  • 原地移除数组元素不是不可实现的，可以考虑用文中的 用最后一个元素替换需要移除的元素 或 用双指针重写整个数组来实现

© AlotOfBlahaj 2022 - 2025