27. 移除元素

[Geekhyt]

原题链接

双指针

先明确题意，题目要求我们原地操作。

1. 借助 left、right 双指针，从起点出发，right 指针指向当前元素，left 指针指向将要赋值的位置
2. 如果右指针指向的元素不等于 val，将右指针指向的元素赋值到左指针的位置，左右指针同时前进一步
3. 如果右指针指向的元素等于 val，那么它不能在最终的输出数组里，左指针不动，右指针前进一步
4. 输出 left 即为数组的长度

在极端情况下，nums 数组中没有元素等于 val，那么左右指针各遍历了一次数组。

const removeElement = function(nums, val) {
    const len = nums.length
    let left = 0
    for (let right = 0; right < len; right++) {
        if (nums[right] !== val) {
            nums[left] = nums[right]
            left++
        }
    }
    return left
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

双指针夹逼

1. 借助双指针，left 从数组的头出发，right 从数组的尾出发，不断向中间夹逼遍历
2. 如果左指针指向的元素等于 val，将右指针指向的元素赋值到左指针的位置，右指针向左移动一步
3. 如果赋值过来的元素也等于 val，那么就继续将右指针指向的元素赋值到左指针的位置，覆盖上一步等于 val 的元素
4. 当左指针指向的元素不等于 val 时，左指针向右移动一步
5. 最后当左指针和右指针相遇时，遍历完成，返回 left 即可

这种方法在极端情况下，左右指针加起来只遍历了数组一次。

const removeElement = function(nums, val) {
    let left = 0
    let right = nums.length
    while (left < right) {
        if (nums[left] === val) {
            nums[left] = nums[right - 1]
            right--
        } else {
            left++
        }
    }
    return left
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)