Remove dups in sorted vector

rawpixel-600789-unsplash

To remove duplicates of an array, use a hash map and array elements as keys, then extract keys. This requires extra space for storing the hash and time. Following algorithm does not need any extra space and time.

The algorithm is uses 3 iterators and moves the duplicate elements at the start of vector and erases the rest of vector. Pseudo code given as follows:

  1. take iterator ​`​start` that points to beginning of vector.
  2. take another iterator `i` that points to next element to start.
  3. move  i to next index until elements are duplicate.
  4. replace start with next element and increase start pointer.
  5. at the end erase elements from start+1 to end from vector.
#include <iostream>  // std::cout 
#include <vector>   
#include <cstdlib>  // std::srand
#include <ctime>    // std::time

int main(){
 std::vector<int> v(100);
 std::srand(std::time(nullptr)); // use current time as seed for random generator
 
// generate 1000 random numbers between 0 to 99
 for(int i = 0; i < 1000; i++){
   int random_variable = std::rand()%100;
   v.push_back(random_variable);
   std::cout << random_variable << ' ';
 }

// sort
std::sort(v.begin(), v.end());


std::vector<int>::iterator start = v.begin();
std::vector<int>::iterator end = v.end();
auto i = start+1; // std::vector<int>::iterator i = start+1;
 while(i != end-1){
   if(*start == *i){
     i++;
   }else{
     start++;
     *start = *i;
   }
 }

v.erase(start+1, end);
 for(const auto & i:v) std::cout << i << ' ';
}

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s