leetcode 27.Remove Element
程序员文章站
2024-03-22 15:04:34
...
Given an array and a value, remove all instances of that value in place and return the new length.
给定一个数列和一个值,将等于这个值的元素移除并返回最后的数列长度。
思路
我首先想到的办法是用一个index, i去遍历数组,若是不等于给定的值,就将另一个index, start所处的位置的值,等于i的位置的值,也就是nums[start] = nums[i],再将start向后移动。
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
start = 0
for i in range(len(nums)):
if nums[i] != val:
nums[start] = nums[i]
start += 1
return start
提交之后,发现耗时比较长,然后看了下discuss里别人的做法,发现特别巧妙。定义一个start和end分别位于数列的最左端和最右端,让start向右遍历,若是等于给定的值,就将这个位置的值与end位置的值交换,并且end位置向左移动一位。这样就可以将所有等于给定值的数都移到start的右边去,最后返回start。
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
start = 0
end = len(nums) - 1
while start <= end:
if nums[start] == val:
nums[start], nums[end], end = nums[end], nums[start], end - 1
else:
start += 1
return start