Skip to content

Latest commit

 

History

History
203 lines (175 loc) · 4.58 KB

0027._remove_element.md

File metadata and controls

203 lines (175 loc) · 4.58 KB
Raw

Navigation

Links:

  1. https://leetcode.com/problems/remove-element/
  2. https://leetcode-cn.com/problems/remove-element/

Tags

  1. 数组
  2. 双指针

Solution 1 Python API

真正意义上的删除。但是由题目的描述得知，可以不用真正地删除。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        frequency = nums.count(val)

        for i in range(frequency):
            nums.remove(val)

        return len(nums)
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0

        while i < len(nums):
            if val == nums[i]:
                nums.pop(i)
            else:
                i += 1

        return len(nums)
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        while val in nums:
            nums.pop(nums.index(val))

        return len(nums)
class Solution:
    def removeElement(self, nums, val): 
        while val in nums:
            nums.remove(val)

        return len(nums)

Solution 2 双指针，相同方向

当nums[fast]与给定的val相等时，则fast继续递增以跳过该元素。
只要nums[fast] != val，就把nums[fast]复制到nums[slow]。
并且快慢指针同时递增。直到fast到达列表的末尾。

用慢指针逐步构建删除元素后的列表，可以用交换或者覆盖方式。

交换

class Solution:
    def removeElement(self, nums, val):
        slow = 0

        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

        return slow

覆盖

class Solution:
    def removeElement(self, nums, val):
        slow = 0

        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1

        return slow                
class Solution(object):
   def removeElement(self, nums, val):
        slow = 0
        for num in nums:
            if num != val:
                nums[slow] = num
                slow += 1
        return slow

Go

func removeElement(nums []int, val int) int {
    left := 0
    for _, v := range nums {    // v is nums[right]
        if v != val {
            nums[left] = v
            left++
        }
    }

    return left
}

Solution 3 双指针，相反方向

一个从头向后扫，一个从尾向前扫，start指针把等于 val 的位置和end指针不等于 val 的位置交换。也就是说，start指针会在等于val的位置停下来，end指针会在不等于val的位置停下来。

class Solution:
    def removeElement(self, nums, val):
        start = 0   
        length = len(nums)
        end = length - 1

        while start < end:
            while start < end and nums[start] != val:  
                start += 1  # 在等于val的位置停下
            while start < end and nums[end] == val:  
                end -= 1     # 在不等于val的位置停下
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

        result = 0
        for i in range(length):
            if nums[i] != val:
                result += 1
        return result
class 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

Go

func removeElement(nums []int, val int) int {
    left, right := 0, len(nums)
    for left < right {
        if nums[left] == val {
            nums[left] = nums[right-1]
            right--
        } else {
            left++
        }
    }
    
    return left
}

Summary

Solution 2和3是在旧列表中逐步构建符合要求的列表。 和0026类似的思想。可以看0026的总结。