27.移除元素

难度：简单

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

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

示例 2：

输入：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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

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

解题思路

这个题目暴力的解法就是两层 for 循环：

外层 for 循环遍历数组元素，查找需要剔除的元素
内层 for 循环将被剔除的元素后面的部分逐个前移。

但这样做的话，时间复杂度为 O(n^2)，有点太高了，而且让数组元素逐个前移的过程感觉很傻，很不优雅。

所以这里我采用 双指针法（快慢指针法）：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作。

先定义一下快慢指针：

快指针：寻找新数组里应该存在的元素，新数组就是不含有目标元素的数组
慢指针：指向新数组最新一个元素的下标位置

算法过程：

快指针在旧数组里从头到尾寻找新数组里应该存在的元素
慢指针负责将这些元素存入新数组

注意，数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

慢指针指向的“新数组”其实是旧数组里已经被快指针检查过的部分，所以可以放心覆盖，同时当快指针到达旧数组尾部的时候，慢指针的位置也代表了新数组的最终长度（指向的是新数组中最后一个元素下标+1的位置，但这刚好是新数组的大小）。

普通的快慢指针法

java

public int removeElement(int[] nums, int val) {
    int slowIndex = 0;
    int fastIndex = 0;
    while (fastIndex < nums.length) {
        if (nums[fastIndex] != val) {
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
        fastIndex++;
    }
    return slowIndex;
}

时间复杂度：O(n)

空间复杂度：O(1)

这种方法的优点是没有改变元素的相对位置，但要移动的元素个数比较多，而且没有利用到题目中新数组中“元素可为任意顺序”的条件。

如果元素可以为任意顺序，那么旧数组里的有些元素其实可以不改变自身的下标，直接进入到新数组里，因此我们可以采用 相向双指针法。

算法过程：

左指针在旧数组里从头到尾寻找新数组里不应该存在的元素
右指针从尾到头寻找新数组里应该存在的元素
每找到符合条件的上述两个元素，就用右指针指向的元素覆盖掉左指针指向的元素（只需覆盖，无需交换）
当两个指针相遇并且不满足 leftIndex <= rightIndex 条件的时候，代表新数组的元素已经集齐
此时 leftIndex 的坐标其实指向的是新数组中最后一个元素下标+1的位置，但这刚好是新数组的大小

相向双指针法

java

public int removeElement(int[] nums, int val) {
    int leftIndex = 0;
    int rightIndex = nums.length - 1;
    while (leftIndex <= rightIndex) {
        // 找左边需要交换的、值等于val的元素
        while (leftIndex <= rightIndex && nums[leftIndex] != val) {
            leftIndex++;
        }
        // 找右边需要交换的、值不等于val的元素
        while (leftIndex <= rightIndex && nums[rightIndex] == val) {
            rightIndex--;
        }
        if (leftIndex <= rightIndex) {
            nums[leftIndex] = nums[rightIndex];
            leftIndex++;
            rightIndex--;
        }
    }
    return leftIndex ;
}

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

显然，这种方法会改变元素的相对位置，但移动的元素比普通的快慢指针法要少很多。

总结

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。

27.移除元素 ​

解题思路 ​

普通的快慢指针法 ​

相向双指针法 ​

总结 ​

27.移除元素

解题思路

普通的快慢指针法

相向双指针法

总结