How to Find Union of Two Sorted Vectors in C++?
In C++, vectors are containers that can change their size dynamically during the runtime. The union of two vectors refers to the collection of all the distinct elements from the two original vectors. In this article, we will learn how we can find the union of two sorted vectors in C++.
Example:
Input: myVector1 ={1,2,3,4,5} myVector2 = {4,5,6,7,8} Output: Union of vectors = {1,2,3,4,5,6,7,8}
Finding Union of Two-Sorted Vectors in C++
To find the union of two sorted std::vector in C++, we can use a std::set container to store the elements of both vectors so that the repeated elements from both vectors will be stored only once and then we can copy back the elements into a resultant vector which will be the union of the given two vectors.
C++ Program to Find the Union of Two Sorted Vectors
C++
// C++ program to find the union of two vectors #include <iostream> #include <set> #include <vector> using namespace std; // Function to find the union of two vectors vector< int > unionVectors(vector< int >& vec1, vector< int >& vec2) { vector< int > ans; // Declare the set to store the unique elements set< int > s; // insert elements from vector 1 into the set for ( int i = 0; i < vec1.size(); i++) { s.insert(vec1[i]); } // insert elements from vector 2 into the set for ( int i = 0; i < vec2.size(); i++) { s.insert(vec2[i]); } // Store the union of both the vectors into a resultant // vector for ( auto it = s.begin(); it != s.end(); it++) { ans.push_back(*it); } return ans; } int main() { // Intialize the two vectors vector< int > vec1 = { 1, 2, 3, 4, 5 }; vector< int > vec2 = { 4, 5, 6, 7, 8 }; // Print elements of both the vectors cout << "Vector 1: " ; for ( auto num : vec1) { cout << num << " " ; } cout << endl; cout << "Vector 2: " ; for ( auto num : vec2) { cout << num << " " ; } cout << endl; // Find the union of the two vectors vector< int > result = unionVectors(vec1, vec2); // Print the union of the two vectors cout << "Union of Vectors: " ; for ( auto num : result) { cout << num << " " ; } return 0; } |
Output
Vector 1: 1 2 3 4 5 Vector 2: 4 5 6 7 8 Union of Vectors: 1 2 3 4 5 6 7 8
Time complexity : O(N + M ), where N is the number of elements in vector 1 and M is number of elements in vector 2
Auxiliary Space: O(N + M)
Contact Us