題目描述:給定一個已排序的整數陣列 nums,就地(in-place)移除重複元素,使每個元素只出現一次,並回傳去重後的元素個數 k。要求陣列的前 k 個位置存放去重後的元素,其餘位置的值無所謂。
解題思路:利用雙指標技巧。由於陣列已排序,所有相同的元素一定相鄰,因此只需比較相鄰元素即可判斷是否重複。
設慢指標 k 為下一個寫入位置(初始值為 1,因為 nums[0] 必定保留),快指標 i 從索引 1 開始掃描整個陣列:
遍歷結束後,k 就是唯一元素的個數,nums[0..k-1] 存放所有唯一元素。
時間複雜度:O(n) — 快指標 i 從頭到尾掃描陣列一次,每個元素只被訪問一次,n 為陣列長度。
空間複雜度:O(1) — 只使用兩個整數指標,所有操作直接在原陣列上進行,不需要額外的輔助空間。
1. If nums is empty, return 0
2. Initialize k = 1 (slow pointer, first element is always unique)
3. For i from 1 to len(nums) - 1: (fast pointer scans entire array)
a. If nums[i] != nums[k-1]: (new unique element found)
- nums[k] = nums[i] (write to next available position)
- k += 1
b. Else: skip (duplicate)
4. Return k (count of unique elements)方法一:STL unique + distance
使用 C++ STL 的 std::unique(nums.begin(), nums.end()) 函式,它會將所有唯一元素移到陣列前端,並回傳新的尾端迭代器。再用 std::distance 計算唯一元素個數。時間複雜度 O(n),空間複雜度 O(1)。程式碼極為簡潔,但面試中通常需要自行實作邏輯。
方法二:使用 Set 輔助(不符合 in-place 要求)
將所有元素插入 set<int>(自動去重),再將 set 的元素依序寫回陣列前 k 個位置。時間複雜度 O(n log n),空間複雜度 O(n)。此方法不符合題目的 in-place 和 O(1) 空間要求,僅作為概念對比。