สมมติว่าเรามีหมายเลขอาร์เรย์ที่เรียงลำดับแล้ว เราต้องลบรายการที่ซ้ำกันออกเพื่อให้องค์ประกอบที่ซ้ำกันปรากฏอย่างมากที่สุดสองครั้งและส่งคืนความยาวใหม่ ในการทำงานนี้เราไม่สามารถใช้พื้นที่พิเศษได้ เราต้องแก้ปัญหานี้ด้วยพื้นที่ O(1) ตัวอย่างเช่น ถ้าอาร์เรย์เป็นเหมือน [0,0,0,1,1,1,1,2,3,3] ผลลัพธ์จะเป็น [0,0,1,1,2,3,3] , ยาว 7
ให้เราดูขั้นตอน -
- len :=2 และ n :=ขนาดของอาร์เรย์
- ถ้า n <=2 ให้คืนค่า n
- สำหรับ i :=2 ถึง n
- ถ้า nums[i] !=nums[len - 2] หรือ nums[i] !=nums[len - 1]
- nums[len] :=nums[i] และเพิ่ม len ขึ้น 1
- ถ้า nums[i] !=nums[len - 2] หรือ nums[i] !=nums[len - 1]
- คืนเลน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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);
} อินพุต
[0,0,0,1,1,1,1,2,3,3]
ผลลัพธ์
7
