C++ 在 0(n+m) 复杂度中搜索多个不同长度数组的交集

Question

目前我有多个不同长度的有序数组

int * arrs[5];
int arrs_length[5];
int arr0[] = {1, 5, 8};
int arr1[] = {1, 2, 3, 5, 7, 10, 11, 15};
int arr2[] = {1, 4, 5, 6};
int arr3[] = {1, 5, 9, 14, 16, 19};
int arr4[] = {1, 2, 4, 5, 6, 9, 9};
arrs[0] = arr0;
arrs_length[0] = sizeof(arr0) / sizeof(int);
arrs[1] = arr1;
arrs_length[1] = sizeof(arr1) / sizeof(int);
arrs[2] = arr2;
arrs_length[2] = sizeof(arr2) / sizeof(int);
arrs[3] = arr3;
arrs_length[3] = sizeof(arr3) / sizeof(int);
arrs[4] = arr4;
arrs_length[4] = sizeof(arr4) / sizeof(int);

我正在尝试输出这些数组的交集。

我首先使用其中一个数组的值创建一个 unordered_map，然后使用计数函数检查它是否存在。当 1 和 5 不对齐时我遇到了问题，但如果它们对齐了它会起作用。

int intersect(int *arrs[], int arrs_length[], int *re_arr, int & re_size){
    unordered_map <int,int> myMap;
    int j=0;
    for (int i=0; i<arrs_length[0]; i++){
        myMap[arrs[0][i]];
    }

谁能告诉我如何正确搜索无序映射并一次搜索多个数组？

Answer 1

您可以维护无序映射并执行以下操作:

您可以为每个数组创建一个空的无序集。然后，您可以对其进行迭代，如果不在当前集合中，则将 +1 添加到全局 map 中的当前元素，并将其添加到集合中。如果它已经存在，请忽略它。

检查完所有数组后，您应该打印 map 中的元素，使它们的值等于数组的数量。

此解决方案与输入的大小成线性关系，因此具有最佳时间复杂度。