סכום לא חופף של שתי סטים


רמת קושי קַל
נשאל לעתים קרובות נאמן אמזון בעברית טיול קוליזה פינטרסט Snapdeal סינופסיס Teradata
מערך חבטות

הצהרת בעיה

הבעיה "סכום לא חופף של שתי קבוצות" קובעת שקיבלת שני מערכים כערכי קלט כ- 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. חצה את מערך ואילו i <n (אורך המערך).
    1. ספרו ואחסנו את התדרים של שני מרכיבי המערך במפה.
  3. הגדר את totalSum ל- 0.
  4. חצו את המפה.
    1. בדוק אם המפה בעלת ערך האלמנט שווה ל -1.
      1. אם נכון, המשך להוסיף את כל האלמנטים ל- totalSum.
  5. החזר TotalSum.

 הסבר

נתנו שני מערכי קלט בהם חלק מהאלמנטים נפוצים. הצהרת הבעיה מבקשת לברר את הסכום הכולל של כל האלמנטים של שני המערכים שאינם נדירים. לשם כך אנו הולכים להשתמש has has. מפת גיבוב עובד עם מפתח וערכים, יהיו לו מפתחות והערך משויך למפתח. אז זה עובד ביחד. נכריז על hashmap ובמפה אחת אנו הולכים לאחסן אלמנטים של שני המערכים במפה עם התדרים שלהם.

דוגמה

הבה נבחן דוגמה: arrA [] = {1,3,4,5,2}, arrB [] = {2,4,6,7,8}

מכיוון ששני המערכים הם באותו גודל n. תוך כדי חציית שני המערכים עלינו לחצות פעם אחת ובזה, נסיים עם האלמנטים והתדרים. לאחר מכן למפה שלנו יהיו הערכים הבאים.

מפה: {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1}.

לאחר הגדרת המשתנה totalSum ל- 0, עלינו לחצות את המפה כדי לקבל את סכום כל האלמנטים הלא-נפוצים. נבדוק את התנאי אם לאלמנט כלשהו יש את התדר, כלומר 1, פשוט נבחר את האלמנט הזה ונוסיף את האלמנט ואת totalSum ונאחסן ל- totalSum.

totalSum = 0,

  • לאלמנט הראשון '1' של המפה יש תדר אחד ולהוסיף אותו ל- totalSum => totalSum + מקש = 1 +0 = 1.
  • האלמנט השני '2' של המפה מכיל תדר 2 ולכן לא ניקח את המפתח הזה מכיוון שהוא נפוץ בשני המערכים.
  • לאלמנט הראשון '3' של המפה יש תדר אחד ולהוסיף אותו ל- totalSum => totalSum + מקש = 1 +1 = 3.
  • האלמנט השני '4' של המפה מכיל תדר 2 ולכן לא ניקח את המפתח הזה מכיוון שהוא נפוץ בשני המערכים.
  • לאלמנט הראשון '5' של המפה יש תדר אחד, אנו מוסיפים אותו ל- totalSum => totalSum + מקש = 1 +4 = 5.

באופן דומה נוסיף 6, 7 ו 8 בסך הכל כיוון שלכולם יש את הערך 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 (n) איפה "N" הוא אורך המערך. מכיוון שהשתמשנו ב- hashmap כל פעולות החיפוש, המחיקה והעדכון נעשות במורכבות הזמן O (1). כך הצלחנו להשיג מורכבות זמן ליניארית.

מורכבות בחלל

O (n) איפה "N" הוא אורך המערך. נדרש מקום לאחסון המרכיבים של שני המערכים במפה.