مجموع غير متداخلين من مجموعتين


مستوى الصعوبة سهل
كثيرا ما يطلب في Accolite أمازون رفع كوليزا Pinterest Snapdeal سينوبسيس مقاومه
مجموعة تجزئة

المشكلة بيان

تنص مشكلة "مجموع مجموعتين غير متراكبين" على أنه تم إعطاؤك مصفوفتين كقيم إدخال مثل arrA [] و arrB [] من نفس الحجم n. أيضًا ، تحتوي كلتا المصفوفتين على عناصر مميزة بشكل فردي وبعض العناصر المشتركة. مهمتك هي معرفة المجموع الإجمالي لجميع العناصر غير المشتركة.

مثال

arrA[] = {1,3,4,5,2}
arrB[] = {2,4,6,7,8}
30

تفسير

العناصر المميزة في المجموعة أعلاه من المصفوفة هي 1 و 3 و 5 و 6 و 7 و 8.

المجموع الكلي = 1+ 3 + 5 + 6 + 7 +8 = 30.

مجموع غير متداخلين من مجموعتين

 

arrA[]={1,3,4,5,2}
arrB[]={3,4,1,5,7}
9

تفسير

جميع العناصر مشتركة لذا سيكون الناتج 0.

خوارزمية

  1. تعلن أ رسم خريطة.
  2. اجتياز مجموعة بينما أنا <ن (طول المصفوفة).
    1. قم بحساب وتخزين ترددات كل من عناصر المصفوفة في الخريطة.
  3. اضبط المجموع على 0.
  4. اجتياز الخريطة.
    1. تحقق مما إذا كانت الخريطة التي تحتوي على قيمة العنصر تساوي 1.
      1. إذا كان هذا صحيحًا ، فاستمر في إضافة جميع العناصر إلى totalSum.
  5. إجمالي العائد

 تفسير

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

مثال

لنأخذ مثالاً على ذلك: arrA [] = {1,3,4,5,2،2,4,6,7,8،XNUMX،XNUMX،XNUMX}، arrB [] = {XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

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

الخريطة: {1: 1 ، 2: 2 ، 3: 1 ، 4: 2 ، 5: 1 ، 6: 1 ، 7: 1 ، 8: 1}.

بعد ضبط المتغير totalSum على 0 ، نحتاج إلى اجتياز الخريطة للحصول على مجموع كل العناصر غير المشتركة. سوف نتحقق من الشرط إذا كان لأي عنصر تردد ، أي 1 ، سنختار فقط هذا العنصر ونضيف ذلك العنصر و totalSum ونخزنه في totalSum.

المجموع = 0 ،

  • العنصر الأول في الخريطة '1' له تردد واحد وأضفه إلى totalSum => totalSum + key = 1 +0 = 1.
  • العنصر الثاني للخريطة '2' له تردد 2 ، لذلك لن نأخذ هذا المفتاح لأنه شائع في كل من المصفوفتين.
  • العنصر الأول في الخريطة '3' له تردد واحد وأضفه إلى totalSum => totalSum + key = 1 +1 = 3.
  • العنصر الثاني للخريطة '4' له تردد 2 ، لذلك لن نأخذ هذا المفتاح لأنه شائع في كل من المصفوفتين.
  • العنصر الأول في الخريطة '5' له تردد واحد ، نضيفه إلى totalSum => totalSum + key = 1 +4 = 5.

وبالمثل ، سنضيف 6 و 7 و 8 في totalSum لأن جميعها لها القيمة 1 كتكرار. إذن سيصبح 1 + 3 + 5 + 6 + 7 +8 = 30.

الإخراج: 30

رمز

التنفيذ في C ++ لمجموعة غير متداخلة من مجموعتين

#include <unordered_map>
#include<iostream>

using namespace std;

int findSum(int arrA[], int arrB[], int n)
{
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++)
    {
        map[arrA[i]]++;
        map[arrB[i]]++;
    }
    int totalSum = 0;
    for (auto sel: map)
        if (sel.second == 1)
            totalSum += sel.first;

    return totalSum;
}
int main()
{
    int arrA[] = { 5, 1, 10, 4, 7 };
    int arrB[] = { 1, 6, 7, 8, 2 };
    int l = sizeof(arrA) / sizeof(arrA[0]);
    cout << findSum(arrA, arrB, l);
    return 0;
}
35

التنفيذ في Java لمجموعة غير متداخلة من مجموعتين

import java.util.HashMap;
import java.util.Map;

class nonOverlappingSum
{
    public static int findSum(int[] A, int[] B, int n)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (map.containsKey(A[i]))
                map.put(A[i], map.get(A[i]) + 1);
            else
                map.put(A[i], 1);

            if (map.containsKey(B[i]))
                map.put(B[i], map.get(B[i]) + 1);
            else
                map.put(B[i], 1);
        }
        int totalSum = 0;
        for (Map.Entry entry : map.entrySet())
        {
            if (Integer.parseInt((entry.getValue()).toString()) == 1)
                totalSum += Integer.parseInt((entry.getKey()).toString());
        }
        return totalSum;

    }
    public static void main(String args[])
    {
        int arrA[] = { 5, 1, 10, 4, 7 };
        int arrB[] = { 1, 6, 7, 8, 2 };
        int l = arrA.length;
        System.out.println(findSum(arrA, arrB, l));
    }
}
35

تحليل التعقيد

تعقيد الوقت

O (ن) أين "ن" هو طول المصفوفة. نظرًا لأننا استخدمنا علامة التجزئة ، فإن جميع عمليات البحث والحذف والتحديث تتم في الوقت المحدد O (1). وهكذا تمكنا من تحقيق تعقيد زمني خطي.

تعقيد الفضاء

O (ن) أين "ن" هو طول المصفوفة. مطلوب مساحة لتخزين عناصر كلا المصفوفتين في الخريطة.