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

2 回答 2

6

union(a, b, c) = union(union(a, b), c), 也是如此intersection()。即，您可以将 n 个集合的并集或交集分解为 2 个集的 n 个并集或交集（正如 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()，除了需要以不同方式计算缓冲区长度：联合的结果可能与输入大小的总和一样大，而不是输入的最小大小。它可能会被重写以减少缓冲区分配。也可以重写递归以使用迭代，与可以编写合并排序以使用迭代相同的方式，但是当前的递归方法无论如何只使用 O(log n) 额外的堆栈空间。

于 2012-11-06T15:25:00.507 回答
1

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


    }
于 2012-11-06T15:32:32.647 回答