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

快慢指针，先赋再移，线性处理

思路：

1. 初始化两个指针，fast 用于遍历数组，slow 对应有效数组的右边界+1。
2. 遍历数组中的每个元素：
   • 遇到非 val，先赋给 slow 处的元素，再右移 slow，这样 [0,slow-1] 中的元素都是非 val。
   • 遇到 val，fast 继续前进，slow 不动。
3. 遍历完成后，slow 指针的位置即为新数组的长度。

class Solution {
    // 从数组中移除指定值，并返回移除后的数组新长度。先赋再移
    public int removeElement(int[] nums, int val) {
        int fast = 0, slow = 0; // 初始化两个指针，fast 用于遍历数组，slow 用于记录有效元素的位置

        // 遍历数组中的每个元素
        while (fast < nums.length) {
            // 遇到非val，先赋给slow位置的元素，再右移slow，确保[0,slow-1]中的元素都是非val
            if (nums[fast] != val) { // 如果当前元素不等于需要移除的值
                nums[slow] = nums[fast]; // 将 fast 指针指向的有效元素复制到 slow 指针位置
                slow++; // slow 指针右移，准备记录下一个有效元素
            }
            fast++; // fast 指针右移，继续遍历数组
        }

        // 当遍历完成后，slow 指针的位置即为新数组的长度，因为 slow 指针前的所有元素都是有效的（不等于 val）
        return slow; // 返回新数组的长度
    }
}

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

注意这个解法和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++， 这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。归根结底你要分清这两个问题中快慢指针之间的元素的类型。 先赋再移和先移再赋是由第一步决定的。去重问题中第一个元素一定会被保留，所以需要先移再赋。移除元素问题中第一个元素可能会被移除，所以需要先赋再移。

// 有序数组去重，先移再赋
int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        // 遇到新元素，先右移slow，再赋给slow位置的元素
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    
    // 数组长度为索引 + 1
    return slow + 1;
}

之所以有这个差异，是因为在移除元素这个问题中，如果第一个元素是val的话，那么我们需要移除第一个元素，直到fast遇到非val的元素， 我们才能确定第一个元素的值，然后slow再前进一位。而去重的话，我们直接就可以保留第一个元素，即slow可以直接前进。

左右指针，跳跃式处理

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 1 时，我们需要把每一个元素都左移一位。

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

思路：

1. 初始化左右指针，left 表示非 val 元素形成的数组的右边界，right 表示 val 形成的数组的左边界。
2. 遍历数组中的每个元素：
   • 遇到非 val，这是合法元素，直接右移 left 即可，下次的循环在 [left+1, right] 中进行
   • 遇到 val，即非法元素，把它换到 right 处，然后左移 right，下次的循环在 [left, right-1] 中进行
3. 遍历完成后，left 指针的位置即为新数组的长度。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            if (nums[left] == val) {
                // 用nums右侧的元素取代左侧的元素。注意left不能右移，因为有可能取代后left处的新元素还是val。
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        
        // 最终[0,left-1]中的数都不是val，所以返回left
        return left;
    }
}

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