使用雙指針進行原地移除元素

題目描述

給定一個數組 nums 和一個值 val，需要將數組中所有等於 val 的元素原地刪除，並返回刪除後數組的新長度。

要求：

• 不使用額外的數組空間
• 只能使用 O(1) 額外空間
• 數組中超過新長度後面的元素可以忽略

示例 1：

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。你不需要考慮數組中超出新長度後面的元素。例如，函數返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。

示例 2：

輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。註意這五個元素可為任意順序。你不需要考慮數組中超出新長度後面的元素。

數據結構知識

本題不涉及特定的數據結構，但需要對雙指針的概念有一定瞭解。

詳細知識點

雙指針

雙指針是一種常用的技巧，通過使用兩個指針在數組或鏈表中遍歷、操作元素。一般情況下，兩個指針起始位置相同，然後根據問題的要求分別移動指針，以便完成所需的操作。

在本題中，我們使用兩個指針 l 和 r：

• l 指針用於遍曆數組，表示當前元素的位置
• r 指針用於記錄不等於目標值的元素，表示當前已處理的不等於目標值的元素個數

解題方案

首先，我們定義兩個指針 l 和 r，初始時均指向數組的第一個元素。

然後，我們開始遍曆數組。噹噹前位置 l 的元素與目標值 val 不相等時，將其複製到指針 r 的位置，並將 r 向後移動一位。這樣，所有不等於 val 的元素都會被移動到數組的前面。

最後返回指針 r 的值，即為刪除目標值後的數組長度。

具體步驟如下：

1. 初始化指針 l 和 r，將其均指向數組的第一個元素
2. 開始遍曆數組，當 l 小於數組長度時執行以下操作：
   • 如果當前位置 l 的元素與目標值 val 不相等：
     • 將當前位置 l 的元素複製到指針 r 的位置
     • 將指針 r 向後移動一位
   • 將指針 l 向後移動一位
3. 返回指針 r 的值，即為刪除目標值後的數組長度

代碼實現

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

複雜度分析

• 時間複雜度：遍歷一次數組，時間複雜度為 O(n)，其中 n 為數組的長度。
• 空間複雜度：只使用了兩個額外指針，空間複雜度為 O(1)。

總結

本題通過使用雙指針的方法，可以在原地刪除數組中的目標值，並返回新數組的長度。雙指針方法具有時間複雜度線性和空間複雜度常數的優勢，是一種高效的解決方案。使用雙指針時需要註意指針移動的條件和順序，以及處理邊界情況。在實際編程中，可以根據具體問題的要求進行相應的調整。