算法刷题笔记【数组】02

27.移除元素

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

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

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

说明: 略

示例 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

拿到这个题目，很容易就能想到暴力解法，张同学@leon-ais 三下五除二就打出了标（错）准（误）答案。

上代码

/************************************************************************ 
> File Name:		removeElement.c 
> Author:			leon-ais 
> Mail:				leon_ais@qq.com 
> Created Time:		Wed 21 Sep 2022 05:43:48 PM CST 
> Description:  	0.错误解法
************************************************************************/
int removeElement(int* nums, int numsSize, int val) {
    int i=0, j=0;
    for (i = 0; i < numsSize; ++i)
    {
        if (val == nums[i])
        {            
            //内层循环注意防止越界
            for (j = i; j < numsSize - 1; ++j)
            {
                nums[j] = nums[j + 1];
            }
            numsSize--;
        }
    }
    return numsSize;
}

//----------运行结果---------
/**
输入：[0,1,2,2,3,4,5,2,2,2,2,2,2,2,2,2,2] 2
输出：[0,1,2,3,4]
预期：[0,1,3,4,5]
*/

原因

分析：从问题代码能看出来，长度len正常减一，判断相等后，用后方元素对前一个元素进行覆盖，循环控制变量i后移，跳过了相邻的后一个元素。

分析完，构造一个更加能体现这个问题的测试用例，例如 [1,2,2,2,2,2,3,4,5] ，可以发现，每次找到要移除的元素后，长度len正确地减了1,，但因为没有 i-- 漏了几个 2，后方所有元素也对该元素进行了覆盖，由于进行了覆盖，少了一个元素，则外层循环控制变量 i 应该保持当前值不变。

想象一下【逆水行舟，不进则退】，而在这里是【for循环，不退则进】

因此，在进入下一次外层循环前，为了保持 i 不变，我们要在 line 11 之后手动地 i - 1。

解决方案：在外层循环中加上 i-- ;

内层循环有两种写法，原理一样，注意防止越界

上代码

/************************************************************************
> File Name:		removeElement.c
> Author:			leon-ais
> Mail:				leon_ais@qq.com
> Created Time:		Wed 21 Sep 2022 05:43:48 PM CST
> Description:  	1.暴力解法
 ************************************************************************/
int removeElement(int* nums, int numsSize, int val){
    int i=0, j=0;
    for (i = 0; i < numsSize; ++i)
    {
        if (val == nums[i])
        {
            //内层循环注意防止越界
            for (j = i; j < numsSize - 1; ++j)
            {
                nums[j] = nums[j + 1];
            }
            numsSize--;
            i--;
        }
    }
    return numsSize;
}

// 内层循环也可以写为
for (j = i + 1; j < len; ++j)
{
    nums[j - 1] = nums[j];
}

优化

在暴力解法中，每次找到待移除的元素，都将后方所有元素都整体前挪一位，这部分操作是可以通过优化来避免的。

具体可以怎么优化？

可不可以直接让后方元素一步到位？

可不可以在一次遍历中删掉所有目标值?

可惜，想象很丰满，现实很骨感，在数组中没有办法真正删除元素，只能通过后方元素迁移这种操作来覆盖原来位置上的值。

想一想，在有多个目标值连续的情况下，既然每趟都往前挪一位很麻烦，为什么不直接一次性往前挪好几位？

那么，我们考虑一下如何实现这种操作。（会发现不知道怎么删？删几个？）

那逆向思考一下，我们没法删，但可以选择留下哪些值——留下不为目标值的其他元素。

很容易想到新开一个数组来做这件事情，但是题目中要求 原地 移除，则可以使用两个指针来做。

上代码

/************************************************************************
> File Name:		removeElement.c
> Author:			leon-ais
> Mail:				leon_ais@qq.com
> Created Time:		Wed 21 Sep 2022 05:43:48 PM CST
> Description:  	2.加个指针保留下非目标值
 ************************************************************************/
int removeElement(int* nums, int numsSize, int val) {
    int i=0, j=0;
    for (i = 0; i < numsSize; ++i)
    {
        if (val != nums[i])
        {
            arr[j++] = nums[i];
        }
    }
    return len;
}

优化一下代码风格，起个高大上的名字：双指针法、快慢指针

上代码

/************************************************************************
> File Name:		removeElement.c
> Author:			leon-ais
> Mail:				leon_ais@qq.com
> Created Time:		Wed 21 Sep 2022 05:43:48 PM CST
> Description:  	3.快慢指针
 ************************************************************************/
int removeElement(int* nums, int numsSize, int val) {
    int fastIndex=0, slowIndex=0;
    for (fastIndex = 0; fastIndex < numsSize; ++fastIndex)
    {
        if (val != nums[fastIndex])
        {
            nums[slowIndex++] = nums[fastIndex];
        }
    }
    return slowIndex;
}

解毕！