移除元素

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

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

分析

初步思考

这个题本质上和上一个题怒刷力扣(删除有序数组中的重复项)是一模一样的。只不过一个是删除重复元素，一个是删除指定元素。

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

继续思考

值得注意的是，题目加了一句话元素的顺序可以改变。，也许这就是两个题之间的真正区别。那么根据这句话，我们能不能进行优化呢？

如上述代码，当我们i和target的值是一样的时候，并且nums[i]的值也不是val的时候，我们会执行 nums[target] = nums[i];，也就是把本来自己的值又重新给自己赋值，这个就是多余的一个操作，但是我们还必须做，那么我们能不能去掉这个多余的操作呢？

既然可以改编顺序，我们只需要将数组中是val的数据更改为后边不是val的数据即可。

那么同样还是需要两个指针，一个指针从左到右指向是val的位置，一个指针从右到左指向不是val的位置。

答案

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

复杂度

• 时间复杂度：O ( n)，其中 n为序列的长度。我们只需要遍历一次该序列。
• 空间复杂度：O(1)。我们只需要定义两个变量，存储我们指针的位置。

总结

这个题的本质上和上一个题怒刷力扣(删除有序数组中的重复项)是一样的，只不过这个题有优化的空间，我们进行了优化。后边的题似乎比之前几个要简单多了。

还有一个值得注意的是，题目中还有这么一段：

说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

这也是基础知识，也经常在面试中遇到，不会的可以参考我往期的文章Java易错点1学习学习。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！