// trying to find out common elements between to vector // as we all know, set_intersection can help us but it has following limitation //1. sorted input means O(n log n) for each //2. output is not in correct order as input was sorted // see this limitations implemented into method2 function // I tried to implement better way instead of set_intersection into method1 function // it searches in unordered_set and hence its O(1) // so overall complexity is O(n) for entire method.... is this true ? // also it maintains order of input while giving us output // but this doesnt work for duplicate values... how to achieve the same ? //1. thanks for suggestion of method3 Schindlabua @ //https://www.sololearn.com/Discuss/2408422/?ref=app #include #include #include #include #include using namespace std; void method1(vector a, vector b) { cout << "Using custom method:\n"; unordered_set us; for(auto& elem : a) us.insert(elem); vector results; for(auto& elem : b) { auto itr = us.find(elem); if (itr!= us.end()) results.emplace_back(elem); } for(auto& elem : results) cout << elem << ","; cout << endl; } void method3(vector a, vector b) { cout << "Using custom method 2:\n"; unordered_map um; for(auto& elem : a) { auto itr = um.find(elem); if(itr== um.end()) um[elem] = 1; else itr->second++; } vector results; for(auto& elem : b) { auto itr = um.find(elem); if (itr!= um.end()) { if(itr->second-- > 0) results.emplace_back(elem); } } for(auto& elem : results) cout << elem << ","; cout << endl; } void method2(vector a, vector b) { cout << "Using Algorithm:\n"; sort(a.begin(),a.end()); sort(b.begin(),b.end()); vector results(max(a.size(),b.size())); auto itr_d = set_intersection(a.begin(),a.end(),b.begin(),b.end(),results.begin()); for(auto itr = results.begin();itr!=itr_d;++itr) cout << *itr << ","; cout << endl; } int main() { vector a {3,4,7,6,5,2,1,8,9,5}; vector b {3,7,5,9,3,1,5}; cout << "Common elements:\n\n"; method1(a,b); cout << endl << endl; method2(a,b); cout << endl << endl; method3(a,b); return 0; }

set_intersection [alternate Implementation]