1641358817(1).png

要点

  1. input： nums->list, val->int . output: k -> int, k is the number of elements remained.
  2. No extra space for another array, O(1) extra memory

代码

  1. class Solution:
  2.     def removeElement(self, nums: List[int], val: int) -> int:
  3.         if(len(nums)==0):
  4.             return 0
  5.         else:
  6.             curr_index = 0
  7.             for i,value in enumerate(nums):
  8.                 if(val!=value):
  9.                     nums[curr_index]=value
  10.                     curr_index+=1
  11.             return curr_index

此题与26.Remove Duplicates from Sorted Array方法是完全一样的。就不过多解释了。

特殊情况

如果val出现在数组的第一项或者最后一项或者出现次数稀少，有没有比上面更快的方法呢？

代码

  1. class Solution:
  2.     def removeElement(self, nums: List[int], val: int) -> int:
  3.         i = 0
  4.         n = len(nums)
  5.         while (i < n):
  6.             if (nums[i] == val):
  7.                 nums[i] = nums[n - 1]
  8.                 n-=1
  9.             else:
  10.                 i+=1
  11.         return n

以上原理是，每当遇到相同项就将其与最后一项调换，并抛弃最后一项。否则继续检查数组中的下一个值。
这样做的好处是line 6 assignment次数等同于相同项出现的次数，与之前方法：我们每次遇到不同项就做一次assignment。所以，当我们知道出现数很少出现的时候，会大大减少assignment statement的数量，从而更快。