目录

题目描述

思路分析

我的题解

题目描述

给你一个数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

思路1：此类问题的通用解法

         left指向数组的第一个元素，right指向数组的最后一个元素。如果left位置的元素为val，那么就将right位置的元素赋值给left，然后将right前移一位（注意，这里的left并没有习惯性的后移），相当于原right位置的数不变，left位置的val被覆盖掉了，那么此时right与0位置之间的数组就是我们需要继续操作的一个“新数组”，原right位置的元素相当于被“移动”到了left位置。如果当left不为val时，就将left后移一个（这么做是为了防止right位置的元素也为val，避免盲目的left后移），当left走过right时循环停止。

        以上的整个过程就相当于，left控制有效数组长度，从头开始遍历，如果left遇到了要删除的val值，left就停止，将right位置的元素放到这个位置。这里相当于将left位置的val丢出数组，将right位置的元素放过来，此时数组的大小相当于减小一位，所以此时需要right前移一位。当left走过right时，即此时left控制的有效数组大小恰好遍历过整个数组，此时整个删除操作就完成了。

思路2：此类问题的通用解法

        解决这题的一个点在于，我们只需要将数组经过一系列操作，将数组的前面部分变成原数组中消去所有val的数组（即目标数组），然后返回其长度即可，所以对于要删除的val，我们根本就不需要关心它最终的去向。

        所以我们可以用双指针的思路来解决这个问题，首先定义left和right两个指针并同时初始化为0，left控制有效数组（即我们要返回的数组）的长度，right表示当前数组遍历的位置。如果当前right位置的元素不是val那么就将right位置的元素赋值给left位置，同时left后移一位、right也后移一位。如果当前right位置的元素等于val，那么就只是right后移一位，left不动(相当于忽略这个元素)。最终left的大小就是我们所要返回的个数。

        上述的思路2具有解决此类有序数组删除问题的通性。例如下方有两个拓展题目，本题是有一个固定的删除数值val，而下方的 26. 删除有序数组中的重复项 这题是删除重复项，不是一个固定的val，但都大同小异。这题只需要将判断right位置的数是否等于val改为right位置的数值是否等于left-1位置的即可。至于 80. 删除有序数组中的重复项 II 这题也是大同小异的，也是将其改为判断right位置的数是否等于left-2位置的数。核心思路是将right位置的数与left控制的有效数组内的数值进行判断。

拓展题目（后附题解）

26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

//26. 删除有序数组中的重复项 - 题解
int removeDuplicates(int* nums, int numsSize)
{int left = 0, right = -1;while(++right < numsSize){ if(right == 0 || nums[right] != nums[left - 1]){nums[left++] = nums[right]; }}return left;
}

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

//80. 删除有序数组中的重复项 II - 题解
int removeDuplicates(int* nums, int numsSize)
{int left = 0, right = -1;while(++right < numsSize){ //判断当前right位置的数插入到left控制的数组中是否符合条件//符合条件的才将其插入数组，否则继续向右。if(right <= 1 || nums[right] != nums[left - 2]) {nums[left++] = nums[right]; }}return left;
}

我的题解

本题的题解

int removeElement(int* nums, int numsSize, int val)
{
/*法1:做右指针从同一端开始，右指针负责遍历，左指针负责替换*/// int left = 0, right = -1; // while (++right < numsSize)// {//     if (nums[right] != val)     //     {//         nums[left] = nums[right];         //         left++;//     }        //     /*如果nums[right]等于val，则left不动，right继续向后走*/// }// //由于是通过left++来控制左指针的，所以left大小刚好为个数，即此时left刚好比下标大1// return left;//法2：将后面的元素将val覆盖   int left = 0, right = numsSize - 1; while(left <= right) //right走到left左侧1个，表示数组遍历完毕。{//如果left位置为val，则将right位置的移过来，为了防止移过来的也是val，所以并不在此时将left右移if(nums[left] == val)         nums[left] = nums[right--];          else     left++;  }return left;}