80. Remove Duplicates from Sorted Array II

題目描述

題目連結：80. Remove Duplicates from Sorted Array II

給定一個已經排序的整數數組 nums，請您在原地刪除重複出現的元素，使得每個元素最多出現兩次，回傳刪除後數組的新長度。不要使用額外的空間，必須在原地修改輸入數組並在O(1)額外空間條件下完成

解題思路

要解決這個問題，我們可以使用two pointer的方法來遍歷陣列並在原地進行修改。具體思路如下：

1. 使用一個指標 i 來標記新的陣列的長度
2. 遍歷陣列中的每一個元素，對於每一個元素 num：
   • 如果 i 小於 2，說明這是陣列前兩個元素，我們直接保留
   • 如果 nums[i-2] != num，說明當前元素不是重複出現三次以上，我們保留它
3. 當決定保留當前元素 num 時
   1. 將它放置在位置 i 上，即 nums[i] = num
   2. 將指針 i 增加 1，表示我們已經成功地將一個元素放入新陣列中，準備處理下一個位置
4. 當數字不被保留: i 不會進行移動，因此該數字會被之後的 nums[i] = num 覆蓋而達成丟棄的效果

這樣，我們就能保證每個元素最多出現兩次，並且 i 就是新陣列的長度

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (const int num : nums) {
            if (i < 2 || nums[i - 2] != num) {
                nums[i++] = num;
            }
        }
        return i;
    }
};

• 時間複雜度: O(n)，其中 n 是陣列的長度
• 空間複雜度為 O(1)