LeetCode|LeetCode 27. 移除元素(C语言) LeetCode27.移除元素(C语言)

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

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

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

Analyze 给定的函数如下：

文章图片

@param nums 一个整数数组

@param numsSize 数组长度

@param val 要移除的元素

@return 移除后的数组长度

此题在题目中隐含了一个条件，不过在示例中体现了，就是题中只是说返回删除后的数组长度，但实际上返回的长度 n 在原数组的前 n 项是不能出现目标元素的，即并不能仅仅返回一个长度，还要把数组的内容修改成符合的值。
这题可以这么考虑，采用双指针从头开始遍历数组，一旦发现要删除的元素，保留一个指针，另一个指针继续向下遍历，直到找到一个非目标元素，此时直接把前面保留的目标元素覆盖，同时，两个指针之间的元素也要一个一个全部由非目标值覆盖，直到有一个指针遍历完数组。可以参考如下例子：

示例2中给定 nums = [0,1,2,2,3,0,4,2]，val = 2，此时 pre 和 last 同时指向 0，0 不是目标元素，两指针同时往右移动直到 2，此时 pre 和 last 都指向 2 这个目标元素，因此 last 留下，pre 继续往前寻找可以覆盖 2 的元素，pre 往右移动 1发现其指向的还是 2，继续往右移动 1，此时指向3这个非目标元素，因此用 pre 指向的 3 覆盖 last 指向的 2 ，然后 pre 和 last 同时右移，这时 last 和 pre 之间的值都是可以舍弃的值了(因为他们之间要么是目标元素，要么是已经用来覆盖目标元素了)，这样循环直到遍历完全，最后数组会变成这样：[0，1，3，0，4，0，4，2] ，此时返回 last 所指向的下标就可以了。

Realization

判断

文章图片

如果 i 指向的不是目标元素就覆盖 j 指向的元素(这里没有判断 j 指向的是不是目标元素，因为如果 j 指向的是目标元素就得覆盖，如果不是的话相当于 i 和 j 都指向同一个值，也就不存在覆盖了)

提交

文章图片

Dictionary 【LeetCode|LeetCode 27. 移除元素(C语言)】双指针或者说快慢指针这种方法在LeetCode中用的十分频繁，因此掌握好双指针的用法不仅可以提高解题效率，对代码的效率也有很大的提高。
附源代码

int removeElement(int* nums, int numsSize, int val){ int i = 0, j = 0; for(i = 0; i < numsSize; i++) { if(nums[i] != val) { nums[j++] = nums[i]; } } return j; }