Java基础学习笔记 0、计算机相关知识了解
2026/10/7 16:35:40
文章目录
- 一、[题目](https://leetcode.cn/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150)
- 二、My thinking
- 2.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],val=3输出：2,nums=[2,2,_,_]解释：你的函数应该返回 k=2,并且 nums 中的前两个元素均为2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。 示例2： 输入：nums=[0,1,2,2,3,0,4,2],val=2输出：5,nums=[0,1,4,0,3,_,_,_]解释：你的函数应该返回 k=5，并且 nums 中的前五个元素为0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。二、My thinking
2.1 分析与算法步骤
- 遍历
- 遇到等于val的数值就删除
2.2 代码实现
这么简单我也写错了（以下为错误示范）：
classSolution:defremoveElement(self,nums:list[int],val:int)->int:foriinrange(len(nums)):ifnums[i]==val:delnums[i]k=len(nums)returnk正序遍历行不通
- 会漏删：因为使用del删除元素后，后面所有元素会向前整体移动，而 i 会 i+1，紧跟在被删元素后面的那个元素被跳过
- 索引越界：因为range(len(nums)) 在循环开始前就锁定为 range(原始长度)
解决以上两个问题的方法是：倒序 （以下为正确示范）
classSolution:defremoveElement(self,nums:list[int],val:int)->int:# 倒着遍历，foriinrange(len(nums)-1,-1,-1):ifnums[i]==val:delnums[i]k=len(nums)returnk2.3 时间和空间复杂度
- 时间复杂度：del nums[i] 这个动作，每删除一次，元素后面所有元素都要往前移动一格，按最坏的情况来看，总移动次数大约为 (n-1) + (n-2) + … + 1 ≈ n²/2，∴ 时间复杂度为 O(n²)
- 空间复杂度：使用了一个i、k两个变量，删除是在原始列表上操作，不额外分配空间，∴ 空间复杂度为 O(1)
三、双指针法
3.1 算法步骤
可以用上次有序数组合并的算法——双指针，只是那个是分离双指针分别指向两个不同数组，这次是快慢双指针——两个指针从同一端出发。快的负责遍历、筛选，将符合筛选的条件的丢给慢指针。
- 定义慢指针
- 用快指针遍历
- 定义筛选条件，将符合筛选条件的元素赋给慢指针，慢指针进1
3.2 代码实现
classSolution:defremoveElement(self,nums:list[int],val:int)->int:k=0# k 为 慢指针foriinrange(len(nums)):# i 为快指针ifnums[i]!=val:nums[k]=nums[i]k+=1returnk除此之外，还可以用对撞指针
- 定义左指针、右指针，分别指向数组的首、尾
- 判断左指针是否指向目标值：若是，将右指针指向的元素赋给左指针指向的，右指针减1；若否，左指针加1（继续寻找）
- 返回左指针
classSolution:defremoveElement(self,nums:List[int],val:int)->int:left=0right=len(nums)-1whileleft<=right:ifnums[left]==val:nums[left]=nums[right]# 把右边的元素搬过来覆盖right-=1# 右边界收缩else:left+=1returnleft3.3 时间和空间复杂度
快慢指针和对撞指针都是将数组元素遍历一遍，区别是前者可以保持数组原有顺序，而后者会打乱。
- 时间复杂度：每个元素最多被访问一次、写一次，∴ O(n)
- 空间复杂度：双指针两个变量，∴ O(1)
四、总结
- 可以使用快慢双指针、对撞双指针移除数组元素
- 如果正序遍历带来一些问题，可以考虑倒序遍历