Given two sorted vectors consisting of unique values between 0 and some known 'n'. And size of one vector (set1) will always be greater than that of candidate vector set2.
Query: Is to determine whether given set2 is a subset of set1 or not?
Is their any better and efficient way of doing this apart from the following implementation in C++11?
#include <iostream>
#include <vector>
bool subSetCheck(std::vector<int> set1, std::vector<int> set2) {
//Set1 & 2 are always sorted and contain only unique integers from 0 to some known 'n'
//Set1 is always larger than Set2 in size
std::vector<int>::iterator it1 = set1.begin();
std::vector<int>::iterator it2 = set2.begin();
bool subSet = true;
for (; (it1 != set1.end()) && (it2 !=set2.end()) ;) {
if ( *it1 == *it2) {++it1; ++it2;}
else if( *it1 > *it2) ++it2;
else ++it1;
}
if (it1 ==set1.end()) subSet = false;
return subSet;
}
int main () {
std::vector<int> set1{0,1,2,3,4};
std::vector<int> set2{0,1,5};
if (subSetCheck(set1,set2)) std::cout << "Yes, set2 is subset of set1." << std::endl;
else std::cout << "No! set2 is not a subset of set1." << std::endl;
return 0;
}
Aucun commentaire:
Enregistrer un commentaire