I am trying to remove the duplicate elements in a sorted vector such that each element appears only once.
My code:
#include <iostream>
#include <vector>
using namespace std;
void removeDuplicates(vector<int> &nums)
{
vector<int>::iterator it;
unsigned int j = 1;
while(j < nums.size()-1)
{
if(nums.at(j) == nums.at(j-1))
{
it = nums.begin()+j;
nums.erase(it);
--j; // for every removal, correct the index
}
j += 1; // increment the index
}
}
int main ()
{
vector <int> vect;
int arr[] = {0,0,1,1,1,1,1,2,2,3,3,4}; // the given array
int arrSize = sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i <= arrSize-1; i++) // assign values to the vector
{
vect.push_back(arr[i]);
}
removeDuplicates(vect);
cout << "The unique vector elements are: ";
for (int i = 0; i < vect.size(); i++)
{
cout << vect[i] << " ";
}
cout << endl;
return 0;
}
When I run the code, the output is
The vector unique elements are: 0 1 2 3 4
The question gives the following instruction:
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
In my code, the Big O time complexity is O(n).
- How can remove the duplicates in-place with a time complexity of O(1)?
Aucun commentaire:
Enregistrer un commentaire