[LeetCode解題攻略] 26. Remove Duplicates from Sorted Array

題目描述

給定一個按非降序排序的整數數組 nums，就地刪除重複項，使得每個元素只出現一次。元素的相對順序應保持相同。然後傳回 nums 中唯一元素的數量。

考慮 nums 的唯一元素的數量為 k，要被接受，您需要執行以下操作：

• 更改陣列 nums，使 nums 的前 k 個元素按照它們最初在 nums 中出現的順序包含唯一元素。 nums 的其餘元素以及 nums 的大小並不重要。
• 返回 k。

範例 1：

輸入：

nums = [1, 1, 2]

輸出：

2, nums = [1, 2, _]

解釋：函數返回的長度為 2，前兩個元素分別是 1 和 2，_ 表示不關心的數字。

範例 2：

輸入：

nums = [0,0,1,1,1,2,2,3,3,4]

輸出：

5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

解釋：函數返回的長度為 5，前五個元素分別是 0、1、2、3 和 4。

解題思路

由於數組已經排序，因此相同的元素會出現在相鄰位置。目標是將每個唯一的元素移動到數組的前部，並刪除重複的部分。

解法總覽：

1. 雙指針法

解法一：雙指針法

思路

使用兩個指針：

• slow 指針指向構建結果數組的最後一個位置。
• fast 指針負責遍歷整個數組。

當 nums[fast] 和 nums[slow] 不同時，將 nums[fast] 的值賦給 nums[slow + 1]，並移動 slow 指針。

程式碼實現

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:  # 處理空數組
            return 0
        
        slow = 0
        for fast in range(1, len(nums)):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

時間與空間複雜度

• 時間複雜度：O(n)，因為 fast 指針遍歷了整個數組一次。
• 空間複雜度：O(1)，只使用了常數級別的額外空間。

總結

雙指針法其邏輯清晰且效率高，並且這是一道難度不高的題目，希望這篇文章能幫助大家清楚理解 LeetCode 第 26 題的解法！