C中n个数组的交集和并集
我有那些正在交叉/联合但只有两个数组的函数。 我需要改进它们以使用narrays：arr = {{1,2,3}，{1,5,6}，…，{1,9}}。
数组是有序的，它们的元素在它们中是唯一的。
示例（交叉点）：
输入：{{1,2,3,4}，{2,5,4}，{4,7,8}}
输出：{4}
arr1 []，arr2 – 数组
m，n – 数组交集函数的长度：
int printIntersection(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; while(i < m && j < n) { if(arr1[i] < arr2[j]) i++; else if(arr2[j] < arr1[i]) j++; else /* if arr1[i] == arr2[j] */ { printf(" %d ", arr2[j++]); i++; } } } 和联合function：
int printUnion(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; while(i < m && j < n) { if(arr1[i] < arr2[j]) printf(" %d ", arr1[i++]); else if(arr2[j] < arr1[i]) printf(" %d ", arr2[j++]); else { printf(" %d ", arr2[j++]); i++; } } while(i < m) printf(" %d ", arr1[i++]); while(j < n) printf(" %d ", arr2[j++]); }
union(a, b, c) = union(union(a, b), c) ，对于intersection() 。 也就是说，你可以将n组的并集或交集分解为n个联合或2组的交集（正如NuclearGhost在对该问题的评论中指出的那样）。 您需要做的是更改当前函数，以便它们构建结果集，而不是立即打印结果。 然后，您可以创建一个单独的function来打印一组。
为了提高效率，您希望采用大致相同大小的联合或集合的交集。 因此，假设所有输入集的大小可能大致相等，那么分而治之的方法应该可以正常工作。
void intersection(int arr1[], int arr2[], int m, int n, int *out) { int i = 0, j = 0; while(i < m && j < n) { if(arr1[i] < arr2[j]) i++; else if(arr2[j] < arr1[i]) j++; else /* if arr1[i] == arr2[j] */ { *out++ = arr2[j++]; i++; } } } void multi_intersection(int n, int **arrays, int *lengths, int *out) { if (n == 2) { intersection(arrays[0], arrays[1], lengths[0], lengths[1], out); } else if (n == 1) { memcpy(out, arrays[0], lengths[0] * sizeof (int)); } else { /* Allocate buffers large enough */ int *buf[2]; int len[2] = { INT_MAX, INT_MAX }; int i; for (i = 0; i < n; ++i) { int which = i < n / 2; if (lengths[i] < len[which]) len[which] = lengths[i]; } buf[0] = malloc(len[0] * sizeof (int)); buf[1] = malloc(len[1] * sizeof (int)); /* Recurse to process child subproblems */ multi_intersection(n / 2, arrays, lengths, buf[0]); multi_intersection(n - n / 2, arrays + n / 2, lengths + n / 2, buf[1]); /* Combine child solutions */ intersection(buf[0], buf[1], len, out); free(buf[0]); free(buf[1]); }
类似的代码适用于multi_union() ，但缓冲区长度需要以不同方式计算：并集的结果可能与输入大小的总和一样大，而不是输入的最小大小。 它可能被重写以减少缓冲区分配。 此外，可以重写递归以使用迭代，同样可以编写mergesort以使用迭代，但是当前的递归方法无论如何仅使用O（log n）额外的堆栈空间。
假设数组中的最大值小于K.N是数组的数量
int Result[K] = {0}; intersection function //input array1 int index = 0; for(; index < arrary1len;index++) { Result[array1]++; } ..... for(index = 0; index < K; index++) { if(Result[index] == N) printf("%d",index); }