首页 > itarticle > 27 remove element

27 remove element

admin 11月 14, 2020 0

Description

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.

My Solution

Python

class (object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        tail = len(nums)-1
        head = 0
        while head <= tail:
            while nums[tail] == val:
                tail = tail-1
                if tail<0:
                    break
            i = head
            for num in nums[i:tail+1]:
                if num == val:
                    nums[head]=nums[tail]
                    nums[tail]=val
                    tail = tail - 1
                    head = head + 1
                    break
                head = head + 1
        return tail+1

想法：分别从两端进行遍历，将head==val的值交换到tail处。head和tail相当于两个指针

Best Solution

Python (Simpler my solution)

def removeElement(self, nums, val):
  start, end = 0, 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

想法：O(n)，本质上和我的方法一致