Xóa phần tử trùng lặp từ mảng đã sắp xếp II trong C++

Giả sử chúng ta có mảng đã sắp xếp nums, ta phải xóa các phần tử trùng lặp tại chỗ (in-place) sao cho mỗi phần tử trùng lặp xuất hiện tối đa hai lần và trả về độ dài mới. Không được dùng bộ nhớ thêm. Phải giải quyết với O(1) không gian. Ví dụ, mảng [0,0,0,1,1,1,1,2,3,3] cho kết quả [0,0,1,1,2,3,3], độ dài 7.

Các bước thực hiện:

• len := 2 và n := kích thước mảng
• nếu n <= 2, return n
• for i := 2 đến n
  • nếu nums[i] != nums[len - 2] hoặc nums[i] != nums[len - 1]
    • nums[len] := nums[i], tăng len 1
• return len

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#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;    } }; main(){    Solution ob;    vector<int> v = {0,0,0,1,1,1,1,2,3,3};    cout << ob.removeDuplicates(v); }

Input

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

Output

7