Set union algorithm using vector in C++
10,728
Solution 1
You can use std::set_union algorithm.
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_union (first, first+5, second, second+5, v.begin());
// 5 10 15 20 25 30 40 50 0 0
v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50
Refer :http://www.cplusplus.com/reference/algorithm/set_union/
Solution 2
Sort the vectors, then merge them like in mergesort, but don't insert duplicates.
vector<int> a, b, c;
sort( a.begin(), a.end());
sort( b.begin(), b.end());
int i = 0, j = 0;
while( i < a.size() && j < b.size())
if( a[ i ] == b[ j ] )
{
c.push_back( a[ i ] );
++i, ++j;
}
else if( a[ i ] < b[ j ] )
c.push_back( a[ i++ ] );
else
c.push_back( b[ j++ ] );
while( i < a.size()) c.push_back( a[ i++ ] );
while( j < b.size()) c.push_back( b[ j++ ] );
Comments
-
Arch1tect almost 2 years
I'm only using
std::vector
in this problem, and I can guarantee no duplicates in each vector (but there isn't any order in each vector). How do I union the vectors I have?Example:
If I have following vectors...
1 1 3 2 5 5 4 2 4 4 2
After the union I should have only two vectors left:
1 2 3 4 5
Again I'm only using vector,
std::set
isn't allowed.