LeekCode面试经典150题之移除元素

面试经典150题之移除元素

一、题目

1.题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

2.题目分析

这是一道移除数组中元素的题目，我们需要做到原地移除，但是题目说了不会去管超过我们返回给它的值之后的数字，因此我们有两种思路：一种是直接将所有等于val的数字全部都移动到第k个数之后（并且这种方法是基于交换的，即整个数组包含的数是没有变的），另一种是将所有不等于val的数直接排到前K个，而不管k之后是否有不等于val的数。下面我将介绍4种方法，并且对我踩的一些坑也简要的说明。

二、具体方法

1.直接用remove（）函数解决

whilevalinnums:nums.remove(val)returnlen(nums)

由于remove（）函数能够直接删去列表中第一个匹配的值，因此直接适用能够删去列表中所有等于val的值。这种方法相对简单，但是前提是我们要知道remove（）函数的用法。

2.新列表承接，再替换

num_true=[iforiinnumsifi!=val]foriinrange(len(num_true)):nums[i]=num_true[i]returnlen(num_true)

我们可以用一个全新的列表来讲数组中所有的符合要求的值全部都记录下来，然后再讲这个新的列表的值按顺序插入到原来的列表中去。这种方法也很简单，不太符合题目的要求，因为题目要求原地排序，不过在日常我们自己的代码中需要的时候可以使用。

下面我将介绍两种相对来说比较有意思的方法

3.以栈的思维来看数组

defremoveElement(self,nums,val):""" :type nums: List[int] :type val: int :rtype: int """stack_size=0forxinnums:ifx!=val:nums[stack_size]=x stack_size+=1returnstack_size

我们将nums数组看做一个栈，在我们没有看这个数组之前，我们没有确定栈里面的任意一个元素，因此初始的栈的大小为0。然后我们遍历数组的元素，如果这个元素不为val，我们就把这个数组压入栈中，并且将栈的大小也进行相应的调整。最后我们返回栈的大小。

4.双指针置换法

defremoveElement(self,nums,val):""" :type nums: List[int] :type val: int :rtype: int """left=0right=len(nums)-1whileleft<=right:if(nums[left]==val)and(nums[right]!=val):temp=nums[right]nums[right]=nums[left]nums[left]=temp left+=1right-=1elif(nums[right]==val):right-=1else:left+=1returnleft

这个方法的核心思路就是要设立两个指针，一个一开始指向最左端，一个刚开始指向最右端。然后将所有为val的值都移到数组的右边。
如果左指针指向的值为val，且有指针指向的值不为val的话，我们就将左指针指向的值和有指针指向的值交换，并且左指针右移，右指针左移。不论左指针是否为val，只要右指针为val，就将右指针左移。（这里我们可以具体的解释一下：如果左指针指向的数不为val，且右指针指向的值为val的话，当前右指针指向的位置已经为val了，所以我们要往前找到不是val的进行再进行操作。如果左右都是，我们可以通过移动右指针来转换为第一种情况）最后一种情况，也就是左指针指向的不是并且右指针指向的也不是，那么我们将左指针向右移动即可，右指针不需要一定（因为右指针指向的人这个地方还可以换成val，但是现在没有换）
最后结束的条件就是左指针比右指针大了，返回值就为左指针的数值。

三、我踩的坑

我一开始些的代码是下面这样的：

defremoveElement(self,nums,val):""" :type nums: List[int] :type val: int :rtype: int """foriinnums:ifi==val:nums.remove(i)returnlen(nums)

乍一看，我的这个代码和前面的第一种方法的代码很像，但是为什么我这样些就不行呢？
因为for i in nums 循环是基于列表迭代器实现的，迭代器会按顺序读取列表的索引（0→1→2→…）。在循环中执行 nums.remove(i) 时，列表长度变短、元素前移，迭代器的指针会跳过部分元素，导致漏删。

后面我又尝试用for i in range (len(nums)):进行迭代 ，但是这样也是错的，一旦在某次循环中又元素删除的话，那么len(nums)就会随着改变，会出现和上面一样的问题。