پیدا کردن عناصری از یک مجموعه که داخل مجموعه دیگری وجود ندارن

Question

اگر من 2 مجموعه داشته باشم

و بخوام عناصری که داخل مجموعه اول هست ولی داخل مجموعه دوم نیست رو پیدا کنم چه روش هایی وجود داره ؟

مثلا 

A = { 1,2,3,4,5,7}
B = {2,5}

khoorji : 0 2 3  5   (khorooji index 1,3,4,7 hast)

 

Answer 1

می تونید 2 تا وکتور به همراه ایندکس های مربوطه بسازید و با استفاده از std::sort اون ها رو مرتب کنید بعد با استفاده از std::set_different چیزی که می خواهید رو بدست بیارید بدی این روش اینه 2 بار باید sort کنید یک بار هم هر 2 تا وکتور رو پیمایش کنید که جالب نیست.در کل هم order میشه max( mlogm, nlogn که m وn سایز 2 مجموعه هستن .

 

راه بهتر اینه که از hash استفاده کنید و چون داخل hash به ایندکس عناصر دسترسی ندارید باید ایندکس به همراه مقدار رو pair کنید .

با این روش با یک بار پیمایش کوچکترین مجموعه میشه عناصری که وجود ندارن رو پیدا کرد . ( مرتبه زمانی average این هست : (O(m هست که m سایز مجموعه ای هست که عناصر داخلش وجود دارن مثلا داخل مثال شما A ) (البته بد ترین حالت میشه mn کهn سایز مجموعه دوم هست و زمانی پیش میاد که همه عناصر داخل مجموعه دوم با هم برابر باشن اگر عنصر تکراری براتون مهم نیست به جای std::unorder_multiset از std::unorder_set استفاده کنید تا بدترین حالت هیچ وقت پیش نیاد)

 

اجرا  : http://coliru.stacked-crooked.com/a/77dc748255c8d6e8

#include <iostream>
#include <unordered_set>

template <class T1,class T2>
class MyPair
{
public:
    MyPair(const T1& a,const T2& b):
        first(a),
        second(b){}
    T1 first;
    T2 second;
};

template <typename T1, typename T2>
bool operator==(const MyPair<T1, T2>& P1, const MyPair<T1, T2>& P2)
{
    return P1.second==P2.second;
}

struct pair_hash {
    inline std::size_t operator()(const MyPair<int,int> & v) const {
        return std::hash<int>()(v.second);
    }
};
int main()
{

    std::unordered_multiset<MyPair<int,int>,pair_hash > a ({{0,1},{1,2}, {2,3},{3,4},{4,5},{5,7}});
    std::unordered_multiset<MyPair<int,int>,pair_hash > b({{0,2},{1,5}});

    for(const auto& pair : a){
        if(b.find(pair) == b.end()){
            std::cout<<"Index : "<<pair.first<<
                       " Value : "<<
                       pair.second<<'\n';
        }
    }
}