samedi 19 janvier 2019

Remove the duplicate elements in a given sorted vector with O(1)

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