27. Remove Element

題目連結：27. Remove Element
難度：Easy

題目說明

給定一個 number array nums, 以及 target value val，讓 number array 中的數值前幾位都不等於 target val ，並且需要直接在原本的 array 上操作，不可以宣告別的變數來儲存，之後再回傳 k 代表陣列中的前幾個元素皆不等於 target val

解題思路

1. 宣告一個指標 k 用來記錄 target val 所在的位置

2. 遍歷整個陣列

   • 當 nums[i] 不等於 val 的話
     -> 將 nums[k] 指定為當前的 nums[i]
     -> k += 1
   • 當 nums[i] 等於 val 的話
     -> 繼續迭代

3. 回傳 k

圖解可看 這裡

• Time Complexity: O(N)
• Space Complexity: O(1)

程式碼

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
        
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k

其他討論

曾經也寫過快慢指針法，概念其實很雷同，都會有兩個指針，一個用來記錄要被置換的位置，一個用來遍歷陣列

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow, fast = 0, 0
        
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                fast += 1
                slow += 1
            else:
                fast += 1
        return slow

參考資料

1. NeetCode(2021-09-14)。Remove Element - Leetcode 27 - Python。摘自 YouTube (2023-09-17)
2. Emily Wang（2023-09-17）。自製簡報 in Canva。摘自 Canva (2023-09-17)