27.移除元素Remove Element
题解双指针1算法流程：复杂度分析PythonJava(待完成)
双指针2算法流程：复杂度分析PythonJava(待完成)
题解
本题难点，原地修改 且在
O
(
1
)
O(1)
O(1)空间下完成
双指针1
算法流程：
定义指针
i
=
0
i=0
i=0从第一个元素开始遍历，对于
n
u
m
s
[
j
]
nums[j]
nums[j]: 判断条件
n
u
m
s
[
j
]
!
=
v
a
l
nums[j]!=val
nums[j]!=val，如果满足，将这个值填入
n
u
m
s
[
i
]
nums[i]
nums[i],并令
i
=
i
+
1
i=i+1
i=i+1,指向下一位置最后一次
i
i
i加了1，所以返回长度时无需加1.
复杂度分析
时间复杂度：
O
(
n
)
O\left(n\right)
O(n),只扫描了一遍空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def removeElement(self
, nums
: List
[int], val
: int) -> int:
n
=len(nums
)
i
=0
for j
in range(n
):
if(nums
[j
]!=val
):
nums
[i
]=nums
[j
]
i
=i
+1
return i
Java(待完成)
双指针2
另外一种双指针写法，首尾交换
算法流程：
定义左指针
l
=
0
l=0
l=0和右指针
r
=
n
r=n
r=n **特别注意：**这里右指针
r
=
n
r=n
r=n，这样可以将很多特例如：[1],1包含在内
执行循环
l
<
r
l<r
l<r
如果
n
u
m
s
[
l
]
=
=
v
a
l
nums[l]==val
nums[l]==val,则交换
n
u
m
s
[
l
]
nums[l]
nums[l]和
n
u
m
s
[
r
]
nums[r]
nums[r],表示，如果左端值等于
v
a
l
val
val,则和右端交换。并令右端
r
=
r
+
1
r=r+1
r=r+1,表示这个位置已经放了
v
a
l
val
val,和下一位置交换若不满足条件，则令左端指向下一元素
l
=
l
+
1
l=l+1
l=l+1 返回
l
l
l,这里因为右指针初始化为
n
n
n,可结合例子，发现i即为最终长度
重点： 一定要结合例子体会右指针初始化为数组长度
n
n
n
复杂度分析
时间复杂度：
O
(
n
)
O\left(n\right)
O(n),只扫描了一遍空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def removeElement(self
, nums
: List
[int], val
: int) -> int:
n
=len(nums
)
l
=0
r
=n
while(l
<r
):
if(nums
[l
]==val
):
nums
[l
],nums
[r
-1]=nums
[r
-1],nums
[l
]
r
=r
-1
else:
l
=l
+1
return l
Java(待完成)
