前端与算法 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% 的用户