Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
What if duplicates are allowed at most twice?
For example,
Given sorted array nums =
Given sorted array nums =
[1,1,1,2,2,3]
,
Your function should return length =
5
, with the first five elements of nums being 1
, 1
, 2
, 2
and 3
. It doesn't matter what you leave beyond the new length.class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int count = 1;
int ans = 0, size = nums.size();
if (size == 0 || size == 1) {
return size;
}
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] != nums[i + 1]) {
nums[ans++] = nums[i];
count = 1;
} else {
count++;
if (count == 2) {
nums[ans++] = nums[i];
}
}
}
nums[ans] = nums[size - 1];
return ans + 1;
}
};
============= Another attempt ==========
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int size = 0, iter = 1, count = 1;
if (nums.size() == 0) {
return size;
}
while (iter < nums.size()) {
if (nums[iter] == nums[size]) {
count++;
if (count == 2) {
nums[size + 1] = nums[iter];
size++;
}
} else {
count = 1;
nums[size + 1] = nums[iter];
size++;
}
iter++;
}
nums.resize(size + 1);
return size + 1;
}
};
============= Optimized ==============
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size()<3) return nums.size(); int index=2; for(int i=2;i<nums.size();i++){ if(nums[i]!=nums[index-2]) nums[index++] = nums[i]; } return index; } };
No comments:
Post a Comment