LeetCode(27)移除元素

今天要练习的题目是：力扣（LeetCode)的第27题，移除元素

题目要求

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

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

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

示例：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度5, 并且nums中的前五个元素均为0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为5 ，而 nums = [0,1,3,0,4,2,2,2] 或 nums = [0,1,3,0,4,0,0,0]，也会被视作正确答案。

提示：

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

解题思路

因为需要原地修改数组，并且无需考虑元素的顺序和数组中超出新长度后面的元素。思路的话就是循环数组，将所有值等于val的元素，替换为非val的元素。依然可以使用双指针算法进行解决。

依旧通过图例的方式来辅助理解每一次循环过程中fast指针和slow指针的变化：

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if(nums.length == 0) {  // 依旧先判断边界值
        return 0
    }
    let fast = 0, slow = 0
    while(fast < nums.length) {
        if(nums[fast] !== val) {
            nums[slow] = nums[fast]  // 先将fast的值赋给slow，再对slow进行移位
            slow+
        }
        fast++
    }
    return slow
}

小结

由于这道题是删除指定的val，所以判断条件里当fast不等于val的时候，slow要先原地替换为fast的值再往前移，而前面两天的题都是先往前移再进行赋值。这里还是要注意变通一下。

引用

力扣LeetCode的第27题-移除元素

双指针技巧秒杀七道数组题目——作者：labuladong