两个数组的交集


难度级别 易得奖学金
经常问 亚马逊 ByteDance Facebook
二进制搜索 哈希 哈希 排序 两指针

在两个数组的交集问题中,我们给出了两个 数组,我们需要打印它们的交集(公共元素)。

使用案列

输入
arr1 [] = {1}
arr2 [] = {2,2}
输出
{2,2}

输入
arr1 = {4,9,5}
arr2 = {9、4、9、8、4}
输出
{4,9}

两个数组相交的算法

计算两个数组中每个元素的频率,然后选择公共部分,该公共部分代表两个数组的交集。

即,

考虑这个例子,
arr1 [] = {1}
arr2 [] = {2,2}
arr1中1的频率是2,arr2中1的频率是2。
arr2中2的频率是2。
因此,交集为{2,2}

上面使用的空间可以按以下方式进行优化:

  1. 建立arr1的频率图,即计算每个元素的频率。
  2. 遍历arr2的每个元素。
  3. 如果该元素存在于步骤1中形成的映射中,则将该元素的频率降低1并打印该元素,如果频率变为0,则从映射中删除该元素。
  4. 对arr3的所有元素重复步骤2。

两个数组的交集的解释

考虑一个例子,
arr1 = {4,9,5}
arr2 = {9、4、9、8、4}

步骤

频率 = {}
迭代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 +米)
空间复杂度= O(N)
其中n是arr1的长度,m是arr2的长度。

參考資料