删除数组元素的经典案例题——leetcode27 移除数组 （五种方法详解，cpp，Java实现）_移除数组元素

一道数组删除元素的题目，题目链接如下：

力扣

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

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

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

方法一：双指针法

这是一种常见的解题方法，我们可以使用两个指针，一个指针遍历数组，另一个指针记录非目标元素的个数。当遇到目标元素时，就跳过它，遇到非目标元素时，就与当前指针所指的元素交换位置。

CPP代码例子：

int removeElement(vector<int>& nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.size(); ++j) {
        if (nums[j] != val) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

Java代码例子：

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; ++j) {
        if (nums[j] != val) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

方法二：双指针法优化

在方法一的基础上，我们可以稍作优化。当要删除的元素比较少时，我们可以将要删除的元素移到数组的末尾，减少了赋值的次数。

CPP代码例子：

int removeElement(vector<int>& nums, int val) {
    int i = 0;
    int n = nums.size();
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    return n;
}

Java代码例子：

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    return n;
}

双指针法优化相比于普通双指针法减少了赋值操作的次数。这个思想实际上就是“对撞双指针+覆盖”法。

方法三：逆序遍历法

这种方法比较巧妙，我们从后向前遍历数组，将要删除的目标元素直接从数组中删掉。这样就不需要频繁地搬移元素了哦~