算法：移除数组中的val的所有元素---双指针[2]

淡淡的烟草味﹌ 2024-03-08 06:33 68阅读 0赞

![在这里插入图片描述][00a0b6f4bc3244498610301823a21bc8.png_pic_center]

#### 1、题目： ####

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

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

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

#### 2、分析特点： ####

*  题目要求：原地移除
 *  移除所有val的元素，则 **`结果数组一定比原数组的长度更短`** 。要求原地移除 > **`我们可以把结果数组直接写在原数组上`** ，并且结果数组是那些非等于val的元素组成的，从位置0开始，到某个位置作为结果数组，而原数组需要从0开始到整个数组的长度进行遍历> 使用双指针。
 *  结果数组的指针：\[0, left\]， 结果数组的目的是收集起来结果，他是left一步步进行加加的。
 *  原数组的指针：\[0, right\]，right <= 原数组长度，right 是用于指向原数组当前的元素是否不会等于val，可以被收集。

#### 3、代码： ####

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

#### 4、复杂度分析： ####

>  *  时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。
>  *  空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

#### 5、总结： ####

本题比较简单，只需要抓住，题意要求：原地移除，原地==>结果只能输出到原数组上面，移除，则结果数组长度比原数组更短。利用结果数组从0，开始left++进行收集，而原数组使用right指针从0开始遍历，判断当前元素是否可以被收集起来。

==> 目的就是收集所有符合条件的元素。

**如果本文对你有帮助的话记得给一乐点个赞哦，感谢！**

[00a0b6f4bc3244498610301823a21bc8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/c0ceffd5c5cc4ddea5b17e0f8308ceac.png