leetcode 27. 移除元素_nums.erase

2023.5.24

题目描述：

        这道题要求我们原地移除元素 ，我第一反应是想到了vector的erase方法，这里先复习以下vector的几种删除元素的方法：

         这里使用第二种，删除指定位置的元素。但是这里有一点要注意：在删除完当前元素时，后面的元素会向前移动。直接看代码：

第一种方法：erase法（本人解）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int n = nums.size();
        for(int i=0; i<n; i++)
        {
            if(nums[i] == val)
            {
                nums.erase(nums.begin()+i);
                i--;  //删除完当前元素，后续元素会向前移动。
                n--;  //元素的size也需要-1。 
            }
        }
        return nums.size();
    }
};

         当然，正常来说不应该使用erase函数，这里我在用个笨方法，双重for循环。

第二种方法：暴力解（本人解）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            if(nums[i] == val)
            {
                for(int j = i; j < n-1; j++)
                {
                    nums[j] = nums[j+1];
                }
                n--;
                i--;
            }
        }
        return n;
    }
};

第三种方法：双指针（快慢指针）

        看了下题解的双指针思路，也是自己敲出来双指针的代码了，舒服。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        int i=0, j=0; //双指针
        int n = nums.size(); //记录新数组的元素个数
        while(j < nums.size())
        {
            if(nums[j] != val)
            {
                nums[i] = nums[j];
                i++;
                j++;
            }
            else
            {
                n--;
                j++;
            }
        }
        return n;
    }
};

        双指针思路还是挺迷妙的，这里是定义了一个快指针一个慢指针，快指针走得快，用于遍历原始数组的元素，看看是否等于val值。 而慢指针走的慢，它用来维护新数组（即目标数组）的元素，接受所有满足条件（即元素值不等于val）的元素。

        这里我一开始while循环里写的是j<n，运行发现出错。 然后自己用手推了一下整个过程，很容易就发现这个错误了，于是改成 j<nums.size()了。 因为n是新数组的长度，而我们这里需要的是原始数组（即nums）的长度。