移除元素

Tips

题目类型: 数组, 快慢指针

相关题目:

• 26. 删除排序数组中的重复项
• 61. 旋转链表
• 80. 删除有序数组中的重复项-ii
• 83. 删除排序链表中的重复元素
• 141. 环形链表
• 142. 环形链表 II
• 234. 回文链表

题目

给你一个数组 nums 和一个值 val, 你需要原地移除所有数值等于 val 的元素, 并返回移除后数组的新长度. 不要使用额外的数组空间, 你必须仅使用 O(1) 额外空间并原地改输入数组.

提示:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

示例

输入: nums = [3, 2, 2, 3], val = 3

输出: 2, 此时 nums 变成了 [ 2, 2, 2, 3 ]

解释: 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2. 你不需要考虑数组中超出新长度后面的元素.

题解

使用快慢指针, 题目跟 26. 删除排序数组中的重复项 题类似.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
  const n = nums.length
  if (n === 0) return 0

  let slow = 0,
    fast = 0

  while (fast < n) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast]
      slow++
    }

    fast++
  }

  return slow
}

Rust

pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
    let n = nums.len();

    if n == 0 {
        return 0;
    }

    let (mut slow, mut fast) = (0, 0);

    while fast < n {
        if nums[fast] != val {
            nums[slow] = nums[fast];
            slow += 1;
        }

        fast += 1;
    }

    slow as i32
}