Given an array nums and a value val, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1: Given nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.It doesn't matter what you leave beyond the returned length.
Example 2: Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5
, with the first five elements of nums
containing 0
, 1
, 3
, 0
, and 4.Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.
思路
因为我经常使用python解题,当我看到这道题之后使用python中列表自带的pop()方法来解决的,就是从头遍历到尾,如果相等的元素我们就直接弹出。遍历到尾部结束。时间复杂度为O(n),空间复杂度为O(1)。
如果我们不使用pop()方法,有没有其他方法可以解决?我想到了两个指针的方法分别指向头和尾,如果遇到和val相等的元素将尾指针指向的元素赋值到头指针的位置。直到头和尾指针相遇结束。时间复杂度为O(n), 空间复杂度为O(1).
第二种思路图示
第一种思路解决代码
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if len(nums) < 1: # 没有元素直接弹出
return 0
i,leng = 0, len(nums) while i < len(nums):
if nums[i] == val: # 相等就弹出,
nums.pop(i)
leng -= 1
else:
i +=1
return len(nums)
第二种思路解决代码
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if len(nums) < 1:
return 0
i,leng = 0, len(nums)-1
while i <= leng:
if nums[i] == val:
nums[i] = nums[leng] # 将尾部的元素进行赋值。
leng -= 1
else:
i+= 1
return leng+1