要删除元素使之高效，可不简单！

编号：27. 移除元素

给出数组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]，则函数将返回新的长度5，而nums的前五个元素将是0、1、3、0、4。

“不需要考虑数组中新长度后面的元素。 “”

思路

有些同学可能说过，多余的要素可以删除。

“要知道，数组的元素按内存地址连续，不能单独删除数组中的某个元素，只能将其复盖。 “”

排列的基础知识是这里的程序员的算法面试，可以看到必须掌握的排列理论知识。

暴力解法

这个主题的暴力解法是两层for循环，一个for循环遍历数组元素，第二个for循环更新数组。

删除过程如下：

很明显，暴力解法的时间复杂度为o(n^2)，这个主题的暴力解法可以在leetcode中度过。

暴力解法C++代码

//时间复杂度： o(n^2) () ) ) ) ) ) ) ) ) )

//空间复杂度： o(1) () ) () ) ) ) ) ) ) ) )。

类解决方案{2}

公共：

intremoveelement (向量序数，国际) {

intsize=nums.size (；

for (英制=0； 大小； I ) {2}

if(nums[I]==val ) (/找到要删除的元素后，将数组合并前移一个位置

for(intj=I1； jsize； j ) {2}

数字1=数字；

}

I----； //下表I以后的数值都向前移动了一位数，所以I也向前移动了一位数

size----； //此时的数组大小-1

}

}

重构；

}

(；

双指针法

双指针法(快速指针法) :“用一个快速指针和慢指针在一个for循环中进行两个for循环的工作。 “”

删除过程如下：

“双指针法(快速指针法)”常见于数组和链表的操作，在考察数组和链表操作的许多问题中使用双指针法。 “”

让我们回顾一下。 我以前说过四个主题使用双指针法。

双指针法将时间复杂度o(n )2)的解法最佳化为o ) n )的解法。 也就是说，降低一位数。 主题如下。

15 .用三数之和18 .四数之和双重指针记录前后指针，实现链表的反转：

206 .翻转链表，使用双指针确认环的存在：

142题.环链表II双指针法在数组和链表中还有很多应用，稍后介绍。

双指针法C++代码：

//时间复杂度： o(n ) ) () ) ) ) ) ) ) ) ) ) )。

//空间复杂度： o(1) () ) () ) ) ) ) ) ) ) )。

类解决方案{2}

公共：

intremoveelement (向量序数，国际) {

intslowIndex=0；

for (信息密度=0； fastIndexnums.size (； 快速索引) {

国际航空母舰！=nums ) {2}

nums=nums=快速索引；

}

}

returnslowIndex；

}

(；

在留言区留下你的想法吧！

--------- -结束-------

关于算法学习的资料总结在github:https://github.com/young yangyang 04/leet代码- master中。 其中还有leet代码刷题攻略、各类型经典主题刷题顺序、思维导图。 看看就一定会得到。

每天8:35小时推送经典算法主题，推送的所有主题不是孤立的，而是浅而深、环环相扣的，梳理算法知识脉络，轻松学习算法！

@代码随想录期待着你的关注！