80 Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums=
[1,1,1,2,2,3],Your function should return length =
5, with the first five elements of nums being1,1,2,2and3. It doesn't matter what you leave beyond the new length.Note: Since I did not understand problem completely at first, I thought it was also worth mentioning here that the idea is credit the new size of
numsin such a way so that who ever uses this function can call it, and then simply get the subvector vector<int>(nums.begin(), nums.begin() + count).I thought it was a pretty cool problem so I tried to optimize my solution until I reached the 90% performance threshold.
Attempt 1: O(n^2) time and O(n) space. Maintain a hash for the duplicates up to a count of 2, or otherwise erase the number from
nums. This is a poor implementation because it does not use the fact that the array is sorted, and it calls erase on a contiguous data structure. Bad bad.int removeDuplicates(vector<int>& nums) {
unordered_map<int, int> int_freq;
int_freq.reserve(nums.size());
for (int i = 0; i < nums.size(); i++) {
if (int_freq.find(nums[i]) != int_freq.end()) {
if (int_freq[nums[i]] <= 1) {
int_freq[nums[i]]++;
}
else {
nums.erase(nums.begin() + i);
i--;
}
}
else
int_freq.insert({ nums[i], 1 });
}
return nums.size();
}
Attempt 2: O(2n) time and O(1) space. Iterate through the numbers and accept the ones that don't contain the same elements 2 indices before it.
int removeDuplicates(vector<int>& nums) {
int it = 0;
for (int n : nums) {
// before a duplicate is even possible or
// if 2 elements before is smaller
if (it < 2 || nums[it - 2] != n)
nums[it++] = n;
}
return it;
}
Attempt 3: O(n) time and O(1) space. Same idea, just separate the logic to start at index 2, rather than zero.
int removeDuplicates(vector<int>& nums) {
int it = 2;
const size_t size = nums.size();
for (int j = it; j < size; j++) {
int check = nums[j];
if (nums[it - 2] != check)
nums[it++] = check;
}
return it > nums.size() ? nums.size() : it;
}
Last modified 4yr ago