题目描述

给你一个数组 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

自己思路

同 26 题方式，还是使用双指针（这次应该是机会了吧，o(╥﹏╥)o）

27. 移除元素 - 图1

代码实现

public int removeElement(int[] nums, int val) {
    int cur = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[cur++] = nums[i];
        }
    }
    return cur;
}

运行结果

复杂度分析

时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

这样的算法在最坏情况下（输入数组中没有元素等于val），左右指针各遍历了数组一次。

双指针优化

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 11 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。

实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

算法

如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。
如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。

当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

代码实现

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

复杂度分析

时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

反思

这个。。。没啥好说的，官方的东西都没想到，双指针，步骤优化。。。。还是得 o(╥﹏╥)o
第一种方式是把数组看成两个，第二种方式是只看成一个，需要删除的信息往后面丢