leetcode | Easy | 26. Remove Duplicates from Sorted Array

LeetCode | Easy | 26. Remove Duplicates from Sorted Array

這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素，並且返回移除後的陣列新長度。由於陣列已經是排序好的，所以所有的重複元素會是相鄰的。
我們需要移除重複的元素，使每個元素最多只出現一次，並返回去重後的陣列長度。不能使用額外的空間，也就是要「就地」修改原來的陣列。

解法：快慢指針

1. 設定兩個指針：一個 slow 指針，用來標記不含重複元素的部分；另一個 fast 指針，遍歷整個陣列。
2. 每當發現 fast 指針指向的元素與 slow 指針指向的元素不相同時，將該元素移動到 slow + 1 的位置，並移動 slow 指針。
3. 當 fast 指針遍歷到陣列末尾時，slow 指針的值加 1 就是新陣列的長度。

時間複雜度：O(n)

由於我們只需要遍歷一次陣列，因此時間複雜度是 O(n)。

C++程式碼：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0;  // slow 指針標記不含重複元素的部分
        
        // 例外處理
        if (nums.empty()) {
            return 0;
        }
        
        for (int fast = 1; fast != nums.size(); ++fast) {
            if (nums[fast] != nums[slow]) {
                ++slow;
                nums[slow] = nums[fast];  // 移動非重複的元素到 slow + 1 的位置
            }
        }
        return slow + 1;  // slow 是索引，所以長度是 slow + 1
    }
};

解釋：

• slow 指針用來標記不含重複元素的部分，fast 指針遍歷整個陣列。
• 每次 fast 發現不相同的元素時，將該元素移動到 slow + 1 的位置，並將 slow 指針向前移動。
• 最後 slow + 1 即為新陣列的長度。