LeetCode 26 Remove Duplicates from Sorted Array - 有序數組去重

題目翻譯

給定一個已排序數組，原地移除重複元素，使每個元素只出現一次，返回新長度。不允許額外空間，須 O(1) 空間完成。例如 [1,1,2] → [1,2]，返回 2。

雙指針法（標準解）

利用有序性：重複元素必相鄰。slow 指向最後一個不重複元素的位置，fast 掃描後續元素。當 nums[fast] != nums[slow] 時，slow++ 並將 nums[fast] 複製到 nums[slow]。

代碼實現

// C++
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.size(); ++fast) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

// Java
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

# Python
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

擴展：允許最多保留 k 個重複 (LeetCode 80)

若題目改為「每個元素最多出現兩次」，只需將判斷條件改為 nums[fast] != nums[slow - 1]（k=2 時），通用形式為 nums[fast] != nums[slow - k + 1]。

複雜度

• 時間：O(n)
• 空間：O(1)

總結

有序數組去重是雙指針最經典的應用之一。關鍵在於利用「有序 ⇒ 重複元素相鄰」的性質，用快指針尋找下一個新值，慢指針記錄擺放位置。面試中寫出標準解後，可主動提及 LeetCode 80 的擴展，展示舉一反三能力。