【代码随想录 | Leetcode | 第二天】数组 | 移除元素

╰+哭是因爲堅強的太久メ 2023-10-13 17:04 28阅读 0赞

## 前言 ##

**欢迎来到[小K][K]的[Leetcode|代码随想录|专题化][Leetcode]专栏，今天将为大家带来双指针法和相向双指针的分享**✨

#### 目录 ####

*  前言
 *  27. 移除元素
 *  总结

--------------------

## 27. 移除元素 ##

✨[题目链接点这里][Link 1]

**给你一个数组 `nums` 和一个值 `val`，你需要 原地 移除所有数值等于`val`的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。**

> 说明:
> 
> > 为什么返回数值是整数，但输出的答案是数组呢?  
> > 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。  
> > 你可以想象内部操作如下:  
> > // `nums` 是以“引用”方式传递的。也就是说，不对实参作任何拷贝  
> > `int len = removeElement(nums, val);`  
> > // 在函数里修改输入数组对于调用者是可见的。  
> > // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。  
> > `for (int i = 0; i < len; i++) { print(nums[i]); }`

示例 1：

输入：nums = [3,2,2,3], val = 3
    输出：2, nums = [2,2]
    解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
    输出：5, nums = [0,1,4,0,3]
    解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
    0 <= nums[i] <= 50
    0 <= val <= 100

✨✨**方法一：暴力解题法，用两个`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;
        }
    };

![在这里插入图片描述][48fe9d20f761402abcf9889c3d99a7f7.png]  
✨✨**方法二：双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**

定义快慢指针

*  快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
 *  慢指针：指向更新 新数组下标的位置  
    **以`nums`为1，2，3，4，3，5为例，有如下图的步骤，上面代表块指针，下面的代表慢指针**  
    ![在这里插入图片描述][241e4a21d92b4f5fb17fe49a3d1fafb0.png]

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

![在这里插入图片描述][fc69624d310b45239fd655806bd4c55f.png]  
✨✨**方法三：相向双指针**

class Solution {
        
    public:
        int removeElement(vector<int>& nums, int val) 
        {
        
            int leftIndex=0,rightIndex=nums.size()-1;
            while(leftIndex<=rightIndex)
            {
        
                //找左边等于val的
                while(leftIndex<=rightIndex && nums[leftIndex]!=val) ++leftIndex;
                //找右边不等于val的
                while(leftIndex<=rightIndex && nums[rightIndex]==val)--rightIndex;
                if(leftIndex<rightIndex) nums[leftIndex++]=nums[rightIndex--];
            }
            return leftIndex;
        }
    };

![在这里插入图片描述][54dcd45117de457fa631aecc98a96969.png]

## 总结 ##

✨**双指针法最重要的是要弄明白快慢指针代表的什么，这才是解题的关键**

[K]: https://blog.csdn.net/qq_72157449?spm=1000.2115.3001.5343
[Leetcode]: https://blog.csdn.net/qq_72157449/category_12293229.html?spm=1001.2014.3001.5482
[Link 1]: https://leetcode.cn/problems/remove-element/submissions/
[48fe9d20f761402abcf9889c3d99a7f7.png]: https://img-blog.csdnimg.cn/48fe9d20f761402abcf9889c3d99a7f7.png
[241e4a21d92b4f5fb17fe49a3d1fafb0.png]: https://img-blog.csdnimg.cn/241e4a21d92b4f5fb17fe49a3d1fafb0.png
[fc69624d310b45239fd655806bd4c55f.png]: https://img-blog.csdnimg.cn/fc69624d310b45239fd655806bd4c55f.png
[54dcd45117de457fa631aecc98a96969.png]: https://img-blog.csdnimg.cn/54dcd45117de457fa631aecc98a96969.png