当前位置：首页 > article >正文

【简单】27.移除元素

article 2025/2/11 1:24:56

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

解题方法

方法1：暴力法

用两个for指针，第一个for指针用来遍历整个数组，如果遇到和val值相等的元素，通过第二个for指针将后面的元素都往前移动一格，具体的动画演示可以参考代码随想录，链接如下：

代码随想录：移动指针
代码示例：

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

时间复杂度：O(n^2)
空间复杂度：O(1)

方法2：双指针法

用两个指针，fast和slow来遍历。其中fast指针用来查找新数组需要的元素，slow用来指新数组的下标，比如val=3的话，如果fast和slow遇到不是3的元素，均向前移动一位；如果fast遇到3，新数组不需要这个元素，那么fast向后移，slow不移，再将fast对应的值覆盖到slow对应的位置上，就实现删除的目的。
动画演示依然可参考代码随想录，链接在上面
代码示例：

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;
    }
};

注意这些实现方法并没有改变元素的相对位置！