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