算法刷题笔记【数组】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;
}
解毕！
