0027. 移除元素 #
- 标签:数组、双指针
- 难度:简单
题目大意 #
描述:给定一个数组 nums
,和一个值 val
。
要求:不使用额外数组空间,将数组中所有数值等于 val
值的元素移除掉,并且返回新数组的长度。
说明:
- $0 \le nums.length \le 100$。
- $0 \le nums[i] \le 50$。
- $0 \le val \le 100$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:快慢指针 #
- 使用两个指针
slow
,fast
。slow
指向处理好的非val
值元素数组的尾部,fast
指针指向当前待处理元素。 - 不断向右移动
fast
指针,每次移动到非val
值的元素,则将左右指针对应的数交换,交换同时将slow
右移。 - 这样就将非
val
值的元素进行前移,slow
指针左边均为处理好的非val
值元素,而从slow
指针指向的位置开始,fast
指针左边都为val
值。 - 遍历结束之后,则所有
val
值元素都移动到了右侧,且保持了非零数的相对位置。此时slow
就是新数组的长度。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。