مهمة أخرى للمجموعات

اهلا بكم جميعا!

أنا أوليغ. التخصص: C ++ / C / OS kernels / drivers / Hardware / network / embedded. أعيش وأعمل في الخارج منذ حوالي عام ونصف. الآن في فنلندا ، قبل ذلك كان هناك بولندا. أخبروني عن خصوصيات الانتقال إلى كلا البلدين قبلي ، من هو المهتم - أكتب ، سأجيب على أسئلتك. لقد كتب الكثير أيضًا عن الحياة في هذه البلدان. لكن في يوم من الأيام سأقدم انطباعاتي عن كليهما في شكل مقال مجاني.

الآن أريد أن أتحدث عن مشكلة قضيت نصف يوم في حلها ، رغم أنها لم تكن تستحق العناء. والشيء المضحك هو أنني قمت بحل بعض المشاكل المماثلة في المقابلات. صادفتها أثناء حفر أحد مشاريعي المنزلية.

لذلك ، بالنظر إلى عدد معين من مجموعات الأعداد الصحيحة ذات الأحجام المختلفة. تحتاج إلى العثور على الأرقام الموجودة في جميع المجموعات باستثناء واحدة. مطلوب أيضًا فهرس المجموعة حيث يكون العنصر مفقودًا.

افترض أن هناك مجموعات {1 ، 2 ، 3} ، {3 ، 0 ، 4} ، {5}. في هذا المثال المصطنع ، يدعي العنصر {3} ، الموجود في مجموعتي الصفر والأولى وغائب في المجموعة الثانية ، أنه اكتشاف. يمكن كتابتها أيضًا كمجموعة {3، 2}. حرفيا ، يتم فك رموز هذا السجل على النحو التالي: القيمة 3 غائبة في المجموعة 2. شرط آخر: فقط الأعداد الصحيحة الموجبة من 1 إلى 64. عناصر كل مجموعة فريدة.

في الأساس ، هذا نوع من التعميم لمشكلة المقابلة الكلاسيكية. تمت صياغة الأخير على النحو التالي: يتم استلام الأرقام عند إدخال كتلة معينة من البرنامج ، من الضروري قطع التكرارات. يمكن حلها بسهولة باستخدام STL البدائية unordered_set. إنه جيد لأنه يحتوي على O (1) - وقت البحث المستمر عن التسلسلات الرقمية القصيرة. في إطار مهمة محدودة ، فهي ممتعة للغاية في الذوق واللون. علاوة على ذلك ، عند إضافة نسخة مكررة إليها ، فإنها ببساطة لن تضيفها. ليس من الضروري أيضًا التحقق من قيمة الإرجاع في هذه الحالة. وهذا يعني أن لدينا حفظًا لثلاثة أسطر من التعليمات البرمجية ، والتي يتم تضمينها على أي حال في تنفيذ النموذج. ولكن نظرًا لأن نطاق الأرقام في مشروعي محدود ، يمكنك الاستغناء عنه على الإطلاق. نعم ، إذا قمت بتوسيع نطاق الأرقام ، فسيتعين استخدام unordered_set أو شيء من هذا القبيل.

للتبسيط ، دعنا نضبط عدد المجموعات على 3. يتم تخزين المجموعة في متجه ، أو متجه قالب STL <vector>. والنتيجة هي مجموعة من أزواج متجه الأرقام غير السالبة <زوج <int ، int >>. في الزوج ، في المقام الأول هو العنصر نفسه ، في الثاني هو فهرس المجموعة حيث لا يوجد.

void PrepareData(const vector<vector<int> >& src, vector<pair<int, int> >& res)
{
    vector<pair<int, int> > data(MAX);               //  
    for(unsigned i(0); i < src.size(); ++i)
    {
        const auto& rf(src[i]);
        for(unsigned j(0); j < rf.size(); ++j)
        {
            ASSERT(((0 < rf[j]) && (MAX > rf[j])) && "!!! An invalid data !!!");
            ++data[rf[j]].first;                              //  
            data[rf[j]].second += i;               //   
        }
    }
    auto fs(((src.size() - 1) * src.size()) >> 1); //   
    for(unsigned i(0); i < data.size(); ++i)         //  
    {
        if(data[i].first == src.size() - 1)              // 
        {
            pair<int, int> cur{i, 0};                       //  
            cur.second = fs - data[i].second;   //  ,   
            res.push_back(cur);
        }
    }
}

1)

2) . . , .

3) data . , , ,

4) , (a[1] + a[n]) * n / 2

5) , ,

6) , ,

هذا كل شيء ، نصف يوم عذاب. الرمز لا يتظاهر بأنه جميل. كانت الرغبة فقط في تقديم فكرة ، أو نهج لحل مثل هذه المشاكل. شكر خاص لإيلياواتارو، الذي نصحني بإيلاء الاهتمام الأمثل لخوارزمياتي.

رابط للرمز https://yadi.sk/d/F2dLt6v_uvjKdQ