黄岐网站制作网站查备案密码

一、题目描述

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

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

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

 二、思路分析

        你拿到了这样的一道题：原地移除数组中所有的元素val。在你的考场上，你知道这场考试对你来说十分重要，看到这道题你不由得震惊住了，过于简单当你看到此题时便拥有了以下思路：定义一个新数组，一一对比然后把符合的放入到新的数组中，不符合的跳过，类似代码如下：

int removeElement(int* nums, int numsSize, int val)
{int arr[] = { 0 };int src = 0;int dest = 0;while (src < numsSize){if (nums[src] == val){src++;}else{arr[dest] = arr[src];}}return arr;
}

        在你思考时已经有人交卷了，所幸时间很长，但你敲写代码时突然弹出一个提示：不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

        你被吓出一声冷汗，所幸没有写那么快，你不由得重新思考，你脑海中浮现了以下画面：一对夫妇，在朝着一个共同得目标前进，一个快一点，一个慢一点，于是跑的快的先去寻找目标，找到了给慢的那一个，然后继续前进，那个慢的也离目标近一点，，但不管跑的快的找没找到，都会走到生命尽头，留下慢的一方。

        想到这你恍然大悟，原本的无厘头也有了思路，于是你敲出如下代码：

三、代码实现（双指针法）

int removeElement(int* nums, int numsSize, int val) {int slow = 0;int fast = 0;                           //一对夫妇，原本都是零起点while (fast < numsSize) {                                     //但是有一个跑得快，一个跑得慢if (nums[fast] != val) {                                //于是跑得快的那个先去寻找共同目标nums[slow] = nums[fast];    //如果找到了，就送给跑得慢的那个slow++;                    //然后跑得慢的那个也就离目标近一点}fast++;                       //但是不管是否找得到，跑得快的那方都一直奔跑到生命的尽头}return slow;                    //最终留下跑得慢的一方
}

        你顺利的完成了考试，在那个下午，那个你恍惚的下午！ 

完！