題目描述
給定一個按非降序排序的整數數組 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。
解題思路
由於數組已經排序，因此相同的元素會出現在相鄰位置。目標是將每個唯一的元素移動到數組的前部，並刪除重複的部分。
解法總覽：
- 雙指針法
解法一：雙指針法
思路
使用兩個指針：
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 題的解法！
