80. Remove Duplicates from Sorted Array II

題目描述

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

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

解題思路

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

1. 初始化指標：使用一個指標 i 來標記新陣列的長度（即下一個要放置元素的位置）。
2. 遍歷陣列：對於陣列中的每一個元素 num：
   • 保留前兩個元素：如果 i < 2，表示目前處於陣列的前兩個位置，我們直接保留該元素。因為題目允許每個元素最多出現兩次。
   • 檢查重複次數：如果 nums[i - 2] != num，表示當前元素 num 與新陣列中倒數第二個元素不相同，說明 num 在新陣列中出現的次數少於兩次，我們保留它。
3. 保留元素：
   • 更新陣列：將元素 num 放置在位置 i 上，即執行 nums[i] = num。
   • 移動指標：將指標 i 增加 1，準備處理下一個位置。
4. 不保留元素：如果當前元素 num 不滿足上述條件，則不保留它，指標 i 不變。該元素將在後續的遍歷中被覆蓋，達到移除的效果。

透過上述方法，我們能夠保證每個元素最多出現兩次，並且最終 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 為陣列 nums 的長度。
  • 分析：我們只需遍歷一次整個陣列，每個元素只被訪問一次，因此時間複雜度為線性。
• 空間複雜度：O(1)。
  • 分析：我們只使用了常數級別的額外空間（例如指標 i 和迴圈中的臨時變數），沒有使用與輸入大小相關的額外空間，符合題目要求的原地演算法。