前端与算法 leetcode 27. 移除元素

---

题目描述

27. 移除元素

概要

题目本身其实挺简单的, 官方解答也说道了 人们可能会对 "就地" 一次感到困惑, 并认为在不复制数组的情况下从数组中删除元素是不可能的

提示

双指针, 仅返回长度, 元素顺序可以更改, 元素很少时

解析

把题中的就地删除理解为覆盖, 也就是说, 只要我们找到一个和 val 一样的值, 我们就把他覆盖掉, 所以我们需要两个指针, 一个快指针用来寻找和比较元素, 一个慢指针用来覆盖元素, 同时可以利用 js 的 length 的特性, 在返回长度之前将数组的长度直接设置为我们计算的长度, 这样的好处是我们可以直观的看到数组的结果, 同时实现了真正意义上的修改原数组

算法

在这里考虑元素很少的情况, 当 nums[j] 与给定的值不等时覆盖, 相等时 length-- 同时跳过该元素, 也就是说最好的情况下, 数组内所有元素都与参数相等, 那么 length 自减到 0 同时直接返回 0, 最坏的情况下所有元素都不等, 全部覆盖的同时返回 length 的, 正常情况只要nums[j]!==val, 我们就把他覆用 j 指向的数值覆盖掉, 并递增 i, 重复这个过程一直到 j 到达数组的末尾, 数组的新长度为length

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
const removeElement = (nums, val) => {if (nums.length === 0) return 0
  let {length} = nums
  let [i, j] = [0, 0]
  while (j < nums.length) {if (nums[j] !== val) {nums[i] = nums[j]
      i++
    } else {length--}
    j++
  }
  nums.length = length
  return length
}

传入 [1, 3, 9, 6] 和 3 的运行结果

3
[1, 9, 6]

执行结果

执行用时 :64 ms, 在所有 javascript 提交中击败了 91.87% 的用户
内存消耗 :33.7 MB, 在所有 javascript 提交中击败了 33.58% 的用户