İki massivin kəsişməsi

İki massivin kəsişməsində ikisini verdik seriallar, onların kəsişməsini (ümumi elementləri) yazdırmalıyıq.

misal

Input
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
Buraxılış
{2, 2}

Input
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}
Buraxılış
{4, 9}

İki massivin kəsişmə alqoritmi

Hər iki massivdəki hər elementin tezliyini hesablayın və iki massivin kəsişməsini təmsil edən ümumi hissəni seçin.

Yəni,

Nümunəni nəzərdən keçirək,
arr1 [] = {1, 2, 2, 1}
arr2 [] = {2, 2}
Arr1-də 1-in tezliyi 2-dir, arr2-də 1-nin 2-si.
Arr2-də 2-nin tezliyi 2-dir.
Beləliklə, kəsişmə {2, 2}

Yuxarıda istifadə olunan yer aşağıdakı kimi optimallaşdırıla bilər,

1. Arr1 üçün tezlik xəritəsini qurun, yəni hər elementin tezliyini sayın.
2. Arr2-nin hər bir elementini tək-tək keçin.
3. Element 1-ci mərhələdə yaradılan xəritədə varsa, həmin elementin tezliyini 1-ə endirin və elementi çap edin, əgər tezlik 0 olarsa, elementi xəritədən çıxarın.
4. Arr3-nin bütün elementləri üçün 2-cü addımı təkrarlayın.

İki massivin kəsişməsinin izahı

Bir nümunəyə baxaq,
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}

Step 1

tezlik = {}
Təkrarlama 1
arr1 [0] = 4, belə ki, freq = {(4 -> 1)}
Təkrarlama 2
arr1 [1] = 9, belə ki, freq = {(4 -> 1), (9 -> 1)}
Təkrarlama 3
arr1 [2] = 5, belə ki, freq = {(4 -> 1), (5 -> 1), (9 -> 1)}

Addım 2, 3 və 4

Təkrarlama 1
arr2 [0] = 9, belə ki, freq = {(4 -> 1), (5 -> 1)} və ans = {9}
Təkrarlama 2
arr2 [1] = 4, belə ki, freq = {(5 -> 1)} və ans = {9, 5}
Təkrarlama 3
arr2 [2] = 9, belə ki, freq = {(5 -> 1)} və ans = {9, 5}
Təkrarlama 4
arr2 [3] = 8, belə ki, freq = {(5 -> 1)} və ans = {9, 5}
Təkrarlama 5
arr2 [4] = 4, belə ki, freq = {(5 -> 1)} və ans = {9, 5}

Pin

İki massivin kəsişməsi üçün JAVA kodu

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

İki massivin kəsişməsi üçün C ++ kodu

#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

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n + m)
Kosmik Mürəkkəblik = O (n)
burada n arr1 uzunluğu və m arr2 uzunluğu.

References