文章目录一、[题目](https://leetcode.cn/problems/remove-element/?envTypestudy-plan-v2envIdtop-interview-150)二、My thinking2.1 分析与算法步骤2.2 代码实现2.3 时间和空间复杂度三、双指针法3.1 算法步骤3.2 代码实现3.3 时间和空间复杂度四、总结一、题目给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。示例1 输入nums[3,2,2,3],val3输出2,nums[2,2,_,_]解释你的函数应该返回 k2,并且 nums 中的前两个元素均为2。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。 示例2 输入nums[0,1,2,2,3,0,4,2],val2输出5,nums[0,1,4,0,3,_,_,_]解释你的函数应该返回 k5并且 nums 中的前五个元素为0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。二、My thinking2.1 分析与算法步骤遍历遇到等于val的数值就删除2.2 代码实现这么简单我也写错了以下为错误示范classSolution:defremoveElement(self,nums:list[int],val:int)-int:foriinrange(len(nums)):ifnums[i]val:delnums[i]klen(nums)returnk正序遍历行不通会漏删因为使用del删除元素后后面所有元素会向前整体移动而 i 会 i1紧跟在被删元素后面的那个元素被跳过索引越界因为range(len(nums)) 在循环开始前就锁定为 range(原始长度)解决以上两个问题的方法是倒序 以下为正确示范classSolution:defremoveElement(self,nums:list[int],val:int)-int:# 倒着遍历foriinrange(len(nums)-1,-1,-1):ifnums[i]val:delnums[i]klen(nums)returnk2.3 时间和空间复杂度时间复杂度del nums[i] 这个动作每删除一次元素后面所有元素都要往前移动一格按最坏的情况来看总移动次数大约为 (n-1) (n-2) … 1 ≈ n²/2∴ 时间复杂度为 O(n²)空间复杂度使用了一个i、k两个变量删除是在原始列表上操作不额外分配空间∴ 空间复杂度为 O(1)三、双指针法3.1 算法步骤可以用上次有序数组合并的算法——双指针只是那个是分离双指针分别指向两个不同数组这次是快慢双指针——两个指针从同一端出发。快的负责遍历、筛选将符合筛选的条件的丢给慢指针。定义慢指针用快指针遍历定义筛选条件将符合筛选条件的元素赋给慢指针慢指针进13.2 代码实现classSolution:defremoveElement(self,nums:list[int],val:int)-int:k0# k 为 慢指针foriinrange(len(nums)):# i 为快指针ifnums[i]!val:nums[k]nums[i]k1returnk除此之外还可以用对撞指针定义左指针、右指针分别指向数组的首、尾判断左指针是否指向目标值若是将右指针指向的元素赋给左指针指向的右指针减1若否左指针加1继续寻找返回左指针classSolution:defremoveElement(self,nums:List[int],val:int)-int:left0rightlen(nums)-1whileleftright:ifnums[left]val:nums[left]nums[right]# 把右边的元素搬过来覆盖right-1# 右边界收缩else:left1returnleft3.3 时间和空间复杂度快慢指针和对撞指针都是将数组元素遍历一遍区别是前者可以保持数组原有顺序而后者会打乱。时间复杂度每个元素最多被访问一次、写一次∴ O(n)空间复杂度双指针两个变量∴ O(1)四、总结可以使用快慢双指针、对撞双指针移除数组元素如果正序遍历带来一些问题可以考虑倒序遍历