LeetCode 80. Remove Duplicates from Sorted Array II [Medium] [C++] 解題筆記

這題給定一個排序好的array，要求每個元素最多只成重複出現 2 次，要求我們刪除多餘的元素，且必須要達到 O(1) space complexity.

EX:

    

        [1,1,1,2,2,3]

Ans: [1,1,2,2,3]

想法:

        因為不能使用額外的空間，因此必須要在原本的 input array 上做修改，這邊主要的想法是利用想個變數 cur 與 next_start，分別紀錄當前元素要放在哪個位置與下一個不同的數字出現時要從哪個位置開始放，從 array 頭開始把原本的array 覆蓋過去，當每個重複數字的出現次數等於2時就把 next_start 設為 cur + 1，表示下一個不同的數字直接把多餘的重複數字覆蓋掉。

Complexity: O(n) time, O(1) space.

完整程式碼:

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        if (nums.empty()) { return 0; }

        // current duplicate count

int cnt = 1;

// cur element's new position

        int cur = 1;

// next different number's start position

        int next_start = 1;

        for (int i = 1; i < nums.size(); i++) {

            if (nums[i] == nums[i - 1]) {

                cnt++;

                if (cnt == 2) {

                    next_start = cur + 1;

                }

            }

            else {

                cur = next_start;

                next_start = cur + 1;

                cnt = 1;

            }

            nums[cur++] = nums[i];

        }        

        return next_start;

    }

};