首页 文章

C中n个数组的交集和并集

提问于
浏览 次
2

我有那些正在交叉/联合但只有两个数组的函数 . 我需要改进它们以使用n阵列：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++;
    }
  }
}

和联合功能：

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++]);
}
c arrays

2 回答

  • 1

    union(a, b, c) = union(union(a, b), c) ， intersection() 也一样 . 即你可以将n组的并集或交集分解为n个联合或2组的交集（正如NuclearGhost在对问题的评论中指出的那样） . 您需要做的是更改当前函数，以便它们构建结果集，而不是立即打印结果 . 然后，您可以创建一个单独的功能来打印一组 .

    为了提高效率，您希望采用大致相同大小的联合或集合的交集 . 因此，假设所有输入集的大小可能大致相等，那么分而治之的方法应该可以正常工作 .

    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）额外的堆栈空间 .

    回复于
  • 6

    假设数组中的最大值小于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);


    }
    回复于

相关问题