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 添加到全局地图中的当前元素，并将其添加到集合中。如果它已经存在，请忽略它。

检查完所有数组后，您应该打印地图的元素，使其值等于数组的数量。

这个解决方案在输入的大小上是线性的，所以它有一个最优的时间复杂度。

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

C++ Searching for the intersect of multiple arrays with different lengths in 0(n+m) complexity

c++

arrays

algorithm

unordered-map