塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-27移除元素

最初想法:

注意:不能用额外的数组空间,只能用O(1)的额外空间,元素顺序可以改变。

从头遍历,mycount记录不同于target的元素个数,将与target不同的元素保存到mycount位置。

1
2
3
4
5
6
7
8
9
10
11
12
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
mycount = 0
for index, elem in enumerate(nums):
if elem != val:
nums[mycount] = elem
mycount += 1
return mycount

不过如果要移除的元素在末尾或开头就比较耗时,如何利用元素顺序可以改变这一条件?从末尾复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def removeElement(nums, val):

firstpoint = 0
lastpoint = len(nums)-1
while firstpoint <= lastpoint:
if nums[firstpoint] == val:#用末尾元素替换
while nums[lastpoint] == val and lastpoint>0:
lastpoint -= 1
if lastpoint <= firstpoint:
break
nums[firstpoint] = nums[lastpoint]
lastpoint -= 1
firstpoint += 1
return firstpoint

改进:

对于被交换的最后一个元素可能是您想要移除的值。但是不要担心,在下一次迭代中,仍然会检查这个元素。

将上一个代码简化下,加个else重新检查。

最终版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def removeElement(nums, val):

firstpoint = 0
lastpoint = len(nums)-1
while firstpoint <= lastpoint:
if nums[firstpoint] == val:#用末尾元素替换
# while nums[lastpoint] == val and lastpoint>0:
# lastpoint -= 1
# if lastpoint <= firstpoint:
# break
nums[firstpoint] = nums[lastpoint]
lastpoint -= 1
else:
firstpoint += 1
return firstpoint
if help:小手一抖点个广告 or 大手一挥资助一下