#快慢指针

移除元素

题目

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

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

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

具体思路

使用快慢指针：

• 快指针用于遍历整个数组；
• 慢指针用于将需要保留的元素放到最终的位置；
  • 只有当需要保留元素时才移动，并且是先复制，然后再移动，表明移动的位置是下一个待填充的位置；
• 最终的数组长度，也就是慢指针指向的索引。

具体代码

Java

class Solution {
    public int removeElement(int[] nums, int val) {
        int cur = 0;
        int res = 0;
        while (res < nums.length) {
            if (nums[res] == val) {
                res++;
            } else {
                nums[cur] = nums[res];
                cur++;
                res++;
            }
        }
        return cur;
    }
}

CPP

include <iostream>
include <vector>
using namespace std;

class Solution
{
public:
        int removeElement(vector<int> &nums, int val)
        {
                int fast = 0, slow = 0;
                while (fast < nums.size())
                {
                        if (nums[fast] != val)
                        {
                                nums[slow] = nums[fast];
                                slow++;
                        }
                        fast++;
                }
                return slow;
        }
};

int main()
{
        Solution s;
        vector<int> test1 = {3, 2, 2, 3};
        vector<int> test2 = {0, 1, 2, 2, 3, 0, 4, 2};
        cout << "test1 = " << s.removeElement(test1, 3) << endl;
        cout << "test2 = " << s.removeElement(test2, 2) << endl;
        return 0;
}