leetcode🧑‍💻 27. 移除元素

2022-05-17 | 2024-04-11 | 335 | 1 分钟

移动交换

解题思路

首先初始化两个指针 slow、fast 指向数组的第一项；

slow 遇到 val 停下；

fast 会一直向后面移动；

当 nums[slow] === val && nums[fast] !== val 的时候，交换 slow、fast 处的值；

重复以上的步骤，直到 fast 指针走到数组最后一位结束，返回 slow 即可；

图解

复杂度

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

代码实现

var removeElement = function (nums, val) {
    let slow = 0;
    let fast = 0;

    while (slow <= fast && fast < nums.length) {
        // 左指针为 val 且 右指针不为 val => 交换位置（val 被放到了后面）
        if (nums[fast] !== val && nums[slow] === val) {
            [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
        }

        // left、right 指针一直向右走，找到第一个 val 的位置，右指针向右走，左指针停下
        if (nums[slow] !== val) {
            slow++;
        }

        fast++;
    }

    return slow;
};

移动复制

解题思路

遍历数组，把 非 val 元素从数组第一项开始替换；

遍历结束后替换到了 inx 项，直接返回 inx；

图解

复杂度

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

代码实现

var removeElement = function (nums, val) {
    let inx = 0;

    for (let index = 0; index < nums.length; index++) {
        const el = nums[index];
        if (el !== val) {
            nums[inx++] = el;
        }
    }

    return inx;
};