【代码随想录刷题记录】LeetCode27移除元素

题目地址

1. 思路

1.1 基本思路及代码的初步实现

基本思路大体上和卡尔老师的想法是一致的，详见代码随想录：数组：移除元素，暴力法大家都能想到，我这里写一下算法时间复杂度为$O(n)$时候的思路（全文都是我思考的过程，不太喜欢照着答案解算法，还是有一个自己的思考过程印象深刻）：

• slow是慢指针，用来记录删除该元素后，每个元素对应的新下标slow
• fast是快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
• i是循环迭代的变量，从0开始到nums.size()-1，也就是数组的全部元素对应的下标

每一次循环，当目标值val和数组nums[i]的值一致的时候，fast应该继续往下走，即fast++，而slow则要保持在原地，因为slow记录的是新数组的下标，如果删除一个数值的话，当前位置的下标因为删除了一个元素，其对应的是该删除的元素的下一个元素，也就是nums[slow]=nums[fast]，fast指向的是新元素的值，slow的值则是fast所指向的新元素的值的下标（相当于向前移动元素）；
当目标值val和数组nums[i]的值不一样的时候，不删除当前元素，fast和slow都继续向前走，但是在向前走之前，还要执行nums[slow]=nums[fast]，因为可能之前还删除过元素，所以还要继续向前移动元素，而且假设在fast和slow都向前走之后才执行nums[slow]=nums[fast]，假如此时fast++后，超出了数组的范围，则fast的值就是不合理的下标值，此时会报错提示越界，所以要在slow++和fast++之前执行nums[slow]=nums[fast]。
而谈到这里，我们还注意到，当i遍历到数组中最后一个元素下标的时候，假如此时nums[i]与val是相等的，则说明最后一个元素也要删除，删除末尾元素，fast不需要再一次移动，因为fast再一次移动就越界了，所以还要在nums[i]与val相等的条件下再加一个判断条件，判断fast是否越界，也就是fast == nums.size()这个条件，然后我们还要返回新数组的长度，如果i遍历到最后，nums[i]与val不相等，则slow和fast都向前移动，slow刚好比新数组的最后元素下标多1（越界），则slow是新数组长度；如果nums[i]与val相等，说明要删除这最后一个元素，此时slow正好指向这个最后删除的元素，也就是新数组越界后的第一个内存位置（对应旧数组的最后一个元素位置），而fast在旧数组的越界1个的位置（nums.size()），此时返回slow也是新数组的长度；假设fast遍历到最后没能遍历到旧数组越界的位置且val与nums[i]相等（比如：[1,2,3,3,3]删去3），我们删除的元素对应的是slow所指向的元素，那删除后，slow自然也是指向新数组越界一个内存位置的地方，也是新数组的长度。
看了这么一大段文字描述，接下来看看代码：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        //每次循环，如果在数组中遇到目标值val，则slow停一下，fast继续走
        //slow停一下是因为，我们删除一个元素后，slow就不能继续再往下遍历，因为删除了一个元素，后面的下标都要减1
        //所以slow停一次，fast继续向前走
        //删几次，slow就停几次，然后把对应的新元素nums[fast]赋值过来
        //slow是每个元素对应的新下标，所以nums[slow] = nums[fast]，这样就能够将新数组的元素和新数组的下标对应起来
        //slow遍历到最后，会在新数组的最后一个元素的下标的基础上slow++
        for(int i = 0; i < nums.size(); i++)
        {
            //当前元素不是要删除的元素，nums[slow] = nums[fast]
            //因为新数组还是旧数组（没删除元素），所以[slow]对应的还是nums[fast]
            //就算之前slow停止了一次，删除了元素，但是到本元素nums[i]的时候
            //由于当前的元素不是要删除的元素，所以新数组和旧数组（之前删过元素的数组）一样
            if(val != nums[i])
            {
                //先执行是防止fast越界（针对旧数组）
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
            //当前是要删除的元素，slow要停一下，fast继续走
            else
            {
                /*当i遍历到数组中最后一个元素下标的时候，
                假如此时nums[i]与val是相等的，
                则说明最后一个元素也要删除，
                删除末尾元素，fast不需要再一次移动，
                因为fast再一次移动就越界了，
                所以还要在nums[i]与val相等的条件下再加一个判断条件，
                判断fast是否越界，也就是fast == nums.size()这个条件*/
                fast++;
                if(fast == nums.size())
                {
                    /*当i遍历到数组中最后一个元素下标的时候，
                    如果nums[i]与val相等，说明要删除这最后一个元素，
                    此时slow正好指向这个最后删除的元素，
                    也就是新数组越界后的第一个内存位置
                    （对应旧数组的最后一个元素位置），
                    而fast在旧数组的越界1个的位置（nums.size()），
                    此时返回slow也是新数组的长度*/
                    return slow;
                }
                else
                {
                    nums[slow] = nums[fast];
                }
            }
            
        }
        /*返回新数组的长度，如果i遍历到最后，
        nums[i]与val不相等，则slow和fast都向前移动
        slow刚好比新数组的最后元素下标多1（越界），
        则slow是新数组长度*/
        /*假设fast遍历到最后没能遍历到旧数组越界的位置且val与nums[i]相等
        （比如：[1,2,3,3,3]删去3），
        我们删除的元素对应的是slow所指向的元素，
        那删除后，slow自然也是指向新数组越界一个内存位置的地方，
        也是新数组的长度。*/
        return slow;
    }
};

1.2 三种基本情况

这个算法能遇到的情况如下：

• 1. 要移除的值在数组的中且不在末尾
• 2. 要移除的值在数组末尾（逻辑上不用移动，直接舍弃末尾）
• 3. 要移除的值不在数组中

下面根据这三种基本情况，我们来模拟一下其运行过程

1.3 模拟运行过程

1.3.1 要移除的值在数组的中且不在末尾

假设有这样一个数组nums[1, 2, 2, 3]，val=2：
i=0：
由于$\text{nums}[i]=\text{nums}[0]=1\ne \text{val}=2$，则

i=1：
由于$\text{nums}[i]=\text{nums}[1]=2=\text{val}=2$，则

又由于$\text{fast}=2\ne \text{nums.size()}=4$，则

注意到，slow在此处停止移动一次，因为找到了要删除的元素
i=2：
由于$\text{nums}[i]=\text{nums}[2]=2=\text{val}=2$，则

又由于$\text{fast}=3\ne \text{nums.size()}=4$，则

注意到，slow在此处停止移动一次，因为找到了要删除的元素

i=3：
由于$\text{nums}[i]=\text{nums}[3]=3\ne \text{val}=2$，则

此时循环结束，可以看到slow恰好是在新数组的越界一个单元的位置，也就是新数组的长度，即return slow，示意图如下：

1.3.1 要移除的值在数组末尾

假设有这样一个数组nums[1, 2, 2, 3]，val=3：
i=0：
由于$\text{nums}[i]=\text{nums}[0]=1\ne \text{val}=3$，则

i=1：
由于$\text{nums}[i]=\text{nums}[1]=2\ne \text{val}=3$，则

i=2：
由于$\text{nums}[i]=\text{nums}[2]=2\ne \text{val}=3$，则

i=3：
由于$\text{nums}[i]=\text{nums}[3]=3=\text{val}=3$，则

又由于$\text{fast}=3\ne \text{nums.size()}=4$，则return slow;

1.3.2 要移除的值不在数组中

假设有这样一个数组nums[1, 2, 2, 3]，val=4：
i=0：
由于$\text{nums}[i]=\text{nums}[0]=1\ne \text{val}=4$，则

i=1：
由于$\text{nums}[i]=\text{nums}[1]=2\ne \text{val}=4$，则

i=2：
由于$\text{nums}[i]=\text{nums}[2]=2\ne \text{val}=4$，则

i=3：
由于$\text{nums}[i]=\text{nums}[3]=3\ne \text{val}=4$，则

1.4 代码进一步优化

至此，算法的解的三种情况我们都举了例子论证完了，但是注意观察，每次i自增的时候，fast在if和else两个条件里都自增，似乎fast可以放到if else条件外面自增，我们还注意到，if条件下，我们先执行的nums[slow]=nums[fast]赋值语句，然后才进行的fast++语句，这就说明，我们不能简单地将fast放在if else条件之外，我们思考一下，我们的if(val!=nums[i])的条件里，是先执行的nums[slow]=nums[fast]赋值语句而后进行的slow和fast向前移动一个单位，这是因为，如果我们先移动，再赋值，当fast移动到数组越界处的时候，nums[slow]=nums[fast]这条语句就会报越界的错误，所以我们需要判断一下fast是否越界，如果越界直接返回slow，并且将else的条件下的代码稍微变动，这样就变成了如下的等价形式（也是可以通过的）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        for(int i = 0; i < nums.size(); i++)
        {
            if(val != nums[i])
            {
                slow++;
                fast++;
                //先移动slow和fast，再判断其是否越界，这样就算fast越界，也能直接返回结果
                if(fast == nums.size())
                {
                    return slow;
                }
                nums[slow] = nums[fast];
            }
            else
            {
                fast++;
                if(fast == nums.size())
                {
                    return slow;
                }
                nums[slow] = nums[fast];
            }
            
        }
        return slow;
    }
};

此时，fast++在两个条件里都有，可以单独拿到if else外面（也是可以通过的）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        for(int i = 0; i < nums.size(); i++)
        {
            fast++;
            if(val != nums[i])
            {
                slow++;
                //先移动slow和fast，再判断其是否越界，这样就算fast越界，也能直接返回结果
                if(fast == nums.size())
                {
                    return slow;
                }
                nums[slow] = nums[fast];
            }
            else
            {
                if(fast == nums.size())
                {
                    return slow;
                }
                nums[slow] = nums[fast];
            }
            
        }
        return slow;
    }
};

然后我们又发现，每次i自增的时候，fast必然自增，是不是可以将fast 和 i等效，直接用fast来进行迭代，而且使用fast进行循环迭代，保证不能越界，因为我们最后返回的是slow，之前的情况下，当i=3的时候，如果要删除的元素不在数组之中，fast++会导致越界，但是我们已经证明slow所指才是我们需要的新数组的长度，于是我们尝试将fast等效i在循环中的迭代作用，我们思考一下，for循环的迭代变量一般是等到for循环中的代码执行后，再进行自增，而我们既然选择fast作为迭代变量进行自增，那么我们就要想方设法先将最上面的fast++语句放到for循环内的最后执行，所以我们还是要看一下之前的代码：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        for(int i = 0; i < nums.size(); i++)
        {
            if(val != nums[i])
            {
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
            else
            {
                fast++;
                if(fast == nums.size())
                {
                    return slow;
                }
                else
                {
                    nums[slow] = nums[fast];
                }
            }
            
        }
        return slow;
    }
};

我们原来的代码中，在if(val != nums[i])条件里，nums[slow] = nums[fast];先执行的初衷是为了防止fast和slow越界，而else条件里加上了防止fast越界的情况，那我们也把else条件里的赋值语句nums[slow] = nums[fast];放到fast++;语句前面来执行，得到了如下代码（顺利通过）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        for(int i = 0; i < nums.size(); i++)
        {
            if(val != nums[i])
            {
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
            else
            {
                nums[slow] = nums[fast];
                fast++;
            }
            
        }
        return slow;
    }
};

我们再进行一下等效变换，将两个if else的条件中的重复部分取出来，nums[slow] = nums[fast];语句在判断条件前，fast++;语句在判断条件后，得到如下代码（顺利通过）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        int fast = 0; //快指针，用来记录删除该元素后，新数组的元素对应旧的数组的下标nums[fast]
        for(int i = 0; i < nums.size(); i++)
        {
            nums[slow] = nums[fast];
            if(val != nums[i])
            {
                slow++;
            }
            fast++;
            
        }
        return slow;
    }
};

此时我们观察，fast自增操作已在循环体内部的最后部分了，那就可以让fast代替i做迭代变量了，修改代码为（顺利通过）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        for(int fast = 0; fast < nums.size(); fast++)
        {
            nums[slow] = nums[fast];
            if(val != nums[fast])
            {
                slow++;
            }       
        }
        return slow;
    }
};

但是修改到这个时候，它的实际复杂度并不好，我们继续思考，有些时候，其实nums[slow] = nums[fast];赋值是没必要的，考虑刚才的例子：
假设有这样一个数组nums[1, 2, 2, 3]，val=2：
i=1：
由于$\text{nums}[i]=\text{nums}[1]=2=\text{val}=2$，则

又由于$\text{fast}=2\ne \text{nums.size()}=4$，则

我们先是移动了fast，然后才进行nums[slow]=nums[fast]的赋值操作，但是我们修改后的代码在此处会这样操作：
先进行一次赋值，这个赋值其实是无效的，在nums[fast]和val相等的时候，我们只需要让slow原地等待一次，fast向前走一次，此时没必要进行赋值一次，只有在不等的时候，赋值是有效的，赋值相当于逻辑上从后向前移动

然后再进行指针的移动：

它将真正从后向前赋值的过程放到了val != nums[fast]中执行，所以下一次循环必须先执行赋值操作再进行slow的自增，我们完全可以把赋值过程放到val != nums[fast]条件中执行，因为我们只需要在不等的情况下移动元素。

1.5 代码最终实现

有了上面这些思考，我们发现，其实还是最开始的思路，相等的情况下，slow等一下（不自增），fast自增，不相等的情况下，slow和fast一起自增，并且还要执行赋值过程，而且要注意是先赋值再让slow自增，原因刚才已经提到了，代码最终优化为（顺利通过）：

class Solution {
public:
    // 引用传递，直接改nums，是改其本身，不是拷贝
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slow
        for(int fast = 0; fast < nums.size(); fast++)
        {
            if(val != nums[fast])
            {
                // 下一次循环必须先执行赋值操作再进行slow的自增（对应上文）
                nums[slow] = nums[fast];
                slow++;
            }       
        }
        return slow;
    }
};