Leetcode：27移除元素

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

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

给你一个数组 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,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

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

这道题的用意是指，不能用额外空间。

不能用额外空间，那就用两个指针。快慢指针，这种设计很巧妙，快指针遍历，慢指针覆盖，因为有筛选，所以原始数组的大小够用

🥬上菜上菜

可以使用双指针法来实现原地算法。具体来说，可以采用快慢指针的策略：快指针（fast）遍历数组，慢指针（slow）指向更新数组的下一个位置。当遇到与 val 相等的元素时，快指针继续前进，跳过这些元素；当遇到不等于 val 的元素时，将其复制到慢指针的位置，然后慢指针前进。这样，所有不等于 val 的元素都被移动到数组的前面，且不需要使用额外的空间。

下面是具体的步骤：

初始化两个指针：fast = 0, slow = 0。
遍历数组，fast 作为遍历的指针，slow 指向下一个可能存放非 val 元素的位置。
如果 nums[fast] 不等于 val，就将 nums[fast] 的值复制到 nums[slow]，然后 slow 前进一位。
fast 指针每次循环都前进一位。
当 fast 遍历完整个数组后，slow 的位置即为新数组的长度。

这种方法之所以高效，是因为它避免了对 val 元素的重复检查和不必要的元素移动。

下面是用C++实现的代码示例：

// 27. Remove Element
#include <iostream>
#include <vector>

using namespace std;

// 快慢指针
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 快指针遍历数组，慢指针按需替换
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

// 当返回slow后，之后nums[]里有多少个元素，同时nums[]slow位置及以前的都已经按要求替换好，slow位置以后的不管了

这段代码中，fast 和 slow 两个指针分别扮演了遍历数组和更新数组的角色。通过这种方式，可以实现原地修改数组，同时只使用 O(1) 的额外空间。

🥬上菜上菜#

🥬上菜上菜