צומת שני מערכים


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית Byte פייסבוק
חיפוש בינארי בליל חבטות מִיוּן שני מצביעים

בצומת של שני מערכי בעיה, נתנו שניים מערכים, עלינו להדפיס את הצומת שלהם (אלמנטים משותפים).

דוגמה

קֶלֶט
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
תְפוּקָה
{2, 2}

קֶלֶט
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}
תְפוּקָה
{4, 9}

אלגוריתם לצומת שני מערכים

חשב את התדירות של כל אלמנט בשני המערכים ובחר את החלק המשותף, המייצג את צומת שני המערכים.

כלומר,

שקול את הדוגמה,
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
התדר של 1 ב- arr1 הוא 2 ושל 2 ב- arr1 הוא 2.
התדירות של 2 ב- arr2 היא 2.
אז הצומת הוא {2, 2}

ניתן לייעל את החלל המשמש לעיל באופן הבא,

  1. בנה את מפת התדרים עבור arr1, כלומר, ספור את התדירות של כל אלמנט.
  2. חצו כל אלמנט של arr2, אחד אחד.
  3. אם האלמנט קיים במפה שנוצרה בשלב 1, הפחית את תדירות האלמנט ב -1 והדפס את האלמנט, אם התדר הופך ל 0, הסר את האלמנט מהמפה.
  4. חזור על שלב 3 עבור כל האלמנטים של arr2.

הסבר לצומת שני מערכים

שקול דוגמה,
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}

שלב 1

freq = {}
איטרציה 1
arr1 [0] = 4, אז, freq = {(4 -> 1)}
איטרציה 2
arr1 [1] = 9, אז, freq = {(4 -> 1), (9 -> 1)}
איטרציה 3
arr1 [2] = 5, אז, freq = {(4 -> 1), (5 -> 1), (9 -> 1)}

שלב 2, 3 ו -4

איטרציה 1
arr2 [0] = 9, אז, freq = {(4 -> 1), (5 -> 1)} ו- ans = {9}
איטרציה 2
arr2 [1] = 4, אז, freq = {(5 -> 1)} ו- ans = {9, 5}
איטרציה 3
arr2 [2] = 9, אז, freq = {(5 -> 1)} ו- ans = {9, 5}
איטרציה 4
arr2 [3] = 8, אז, freq = {(5 -> 1)} ו- ans = {9, 5}
איטרציה 5
arr2 [4] = 4, אז, freq = {(5 -> 1)} ו- ans = {9, 5}

צומת שני מערכים

קוד JAVA לצומת שני מערכים

import java.util.HashMap;

public class IntersectionOfTwoArrays {
    private static void printIntersection(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        // Build the frequency map for arr1
        for (int i = 0; i < arr1.length; i++) {
            if (map.containsKey(arr1[i])) {
                map.put(arr1[i], map.get(arr1[i]) + 1);
            } else {
                map.put(arr1[i], 1);
            }
        }

        // Traverse the elements of arr2 one by one
        for (int i = 0; i < arr2.length; i++) {
            // If the map contains current element
            if (map.containsKey(arr2[i])) {
                // Reduce the frequency by 1
                int freq = map.get(arr2[i]);
                freq--;
                // If freq becomes 0, remove the element from the map
                if (freq == 0) {
                    map.remove(arr2[i]);
                } else {
                    map.put(arr2[i], freq);
                }
                // Print the element
                System.out.print(arr2[i] + " ");
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {1, 2, 2, 1};
        int arr2[] = new int[] {2, 2};

        printIntersection(arr1, arr2);

        // Example 2
        int arr3[] = new int[] {4, 9, 5};
        int arr4[] = new int[] {9, 4, 9, 8, 4};

        printIntersection(arr3, arr4);
    }
}
2 2 
9 4

קוד C ++ לצומת שני מערכים

#include<bits/stdc++.h> 
using namespace std;

void printIntersection(int *arr1, int *arr2, int n, int m) {
    unordered_map<int, int> map;
    // Build the frequency map for arr1
    for (int i = 0; i < n; i++) {
        auto it = map.find(arr1[i]);
        if (it != map.end()) {
            it->second = it->second + 1;
        } else {
            map.insert(make_pair(arr1[i], 1));
        }
    }
    
    // Traverse the elements of arr2 one by one
    for (int i = 0; i < m; i++) {
        auto it = map.find(arr2[i]);
        // If the map contains current element
        if (it != map.end()) {
            // Reduce the frequency by 1
            it->second = it->second - 1;
            // If freq becomes 0, remove the element from the map
            if (it->second == 0) {
                map.erase(arr2[i]);
            }
            // Print the element
            cout<<arr2[i]<<" ";
        }
    }
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 2, 1};
    int arr2[] = {2, 2};
    
    printIntersection(arr1, arr2, sizeof(arr1)/ sizeof(arr1[0]), 
            sizeof(arr2) / sizeof(arr2[0]));
            
    // Example 2
    int arr3[] = {4, 9, 5};
    int arr4[] = {9, 4, 9, 8, 4};
    
    printIntersection(arr3, arr4, sizeof(arr3) / sizeof(arr3[0]), 
            sizeof(arr4) / sizeof(arr4[0]));
}
2 2 
9 4

ניתוח מורכבות

מורכבות זמן = O (n + m)
מורכבות שטח = O (n)
כאשר n הוא אורך arr1 ו- m הוא אורך arr2.

הפניות