Remove Duplicates from Sorted Array II - ลบซ้ำสูงสุด 2 ครั้งใน C++

ภาพรวมปัญหา

มีอาร์เรย์จัดเรียงแล้ว ต้องลบค่าซ้ำในที่เดียว (in-place) ให้ค่าซ้ำเหลือสูงสุด 2 ครั้ง คืนความยาวใหม่ ใช้พื้นที่ O(1)

ตัวอย่าง: [0,0,0,1,1,1,1,2,3,3] → [0,0,1,1,2,3,3], ความยาว = 7

อัลกอริทึม (Two Pointers)

1. len = 2, n = ขนาดอาร์เรย์
2. ถ้า n ≤ 2: return n
3. for i = 2 ถึง n-1:
   • ถ้า nums[i] != nums[len-2] หรือ nums[i] != nums[len-1]:
     • nums[len] = nums[i], len++
4. return len

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = 2;
        int n = nums.size();
        if(n <= 2) return n;
        for(int i = 2; i < n; i++){
            if(nums[i] != nums[len - 2] || nums[i] != nums[len - 1]){
                nums[len] = nums[i];
                len++;
            }
        }
        return len;
    }
};

int main(){
    Solution ob;
    vector<int> v = {0,0,0,1,1,1,1,2,3,3};
    cout << ob.removeDuplicates(v);
}

Input / Output

Input:  [0,0,0,1,1,1,1,2,3,3]
Output: 7