算法(3)-移除元素与快慢指针

数组

 2024/03/06 

题目(easy)：

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

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

思路

暴力解法就是两层遍历，第一层遍历数组，第二层更新数组，时间复杂度是 O(n^2)。

双指针法

通过一个快指针和一个慢指针在一个 for 循环完成两个 for 循环的工作。

const removeElement = (nums, val) => {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[k++] = nums[i];
        }
    }
    return k;
}

时间复杂度：O(n)。
空间复杂度：O(1)。

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/06/2024-03-06-%E7%AE%97%E6%B3%95(3)-%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0%E4%B8%8E%E5%BF%AB%E6%85%A2%E6%8C%87%E9%92%88/

发表日期：March 6th 2024, 8:05:12 pm

更新日期：March 6th 2024, 8:31:12 pm

Next Post

算法(4)-有序数组的平方与左右指针
Previous Post

算法(2)-二分查找

CATALOG

1. 题目(easy)：
2. 思路
1. 2.1. 双指针法