交，并用C正阵列 [英] intersection and union of n-arrays in C

问题描述

我有那些正在路口/工会只是两个阵列功能。
我需要太多改善他们正阵列工作：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男，INT N）
{
  INT I = 0，J = 0;
  而（I＆LT; M＆放大器;＆放大器; J＆LT; N）
  {
    如果（ARR1 [1]  - ; ARR2 [J]。）
      我++;
    否则，如果（ARR2 [J]＆LT; ARR1 [I]）
      J ++;
    否则/ *如果ARR1 [I] == ARR2 [J] * /
    {
      的printf（％d个，ARR2 [J ++]）;
      我++;
    }
  }
}
 

和工会的功能：

  INT printUnion（INT ARR1 []，INT ARR2 []，INT男，INT N）
{
  INT I = 0，J = 0;
  而（I＆LT; M＆放大器;＆放大器; J＆LT; N）
  {
    如果（ARR1 [1]  - ; ARR2 [J]。）
      的printf（％d个，ARR1 [我++]）;
    否则，如果（ARR2 [J]＆LT; ARR1 [I]）
      的printf（％d个，ARR2 [J ++]）;
    其他
    {
      的printf（％d个，ARR2 [J ++]）;
      我++;
    }
  }  而（ⅰ＆所述M）
   的printf（％d个，ARR1 [我++]）;
  而（J＆LT; N）
   的printf（％d个，ARR2 [J ++]）;
}
 

解决方案

工会（A，B，C）=工会（工会（A，B），C） ，和同样为路口（）。即你可以分解工会或n组相交成N工会或2台路口（如NuclearGhost在关于这个问题的评论所指出的）。你需要做的是改变你目前的职能，使他们建立一个结果集，而不是立即打印结果。那么你可以让一个单独的函数，它打印一组。

为了提高效率，你想利用套是大致相等大小的集或交集。因此，分而治之的办法应该工作好了，假设所有的输入集都可能是大致相等的大小。

 无效路口（INT ARR1 []，INT ARR2 []，诠释男，诠释N，INT *总分）
{
  INT I = 0，J = 0;
  而（I＆LT; M＆放大器;＆放大器; J＆LT; N）
  {
    如果（ARR1 [1]  - ; ARR2 [J]。）
      我++;
    否则，如果（ARR2 [J]＆LT; ARR1 [I]）
      J ++;
    否则/ *如果ARR1 [I] == ARR2 [J] * /
    {
      *总分++ = ARR2 [J ++];
      我++;
    }
  }
}无效multi_intersection（INT N，INT **阵列，为int *长度，为int *出）{
  如果（N == 2）{
    交点（数组[0]，阵列[1]，长度[0]，长度[1]，出）;
  }否则如果（N == 1）{
    的memcpy（出，数组[0]，长度[0] *的sizeof（INT））;
  }其他{
    / *分配大的缓冲区足够* /
    为int * BUF [2];
    INT LEN [2] = {INT_MAX，INT_MAX};
    INT I;
    对于（i = 0; I＆LT; N ++我）{
      其中INT = I＆LT; N / 2;
      如果（长度[1]  - ; LEN [其中]）len个[其中] =长度[I];
    }
    BUF [0] = malloc的（LEN [0] *的sizeof（int）的）;
    BUF [1] = malloc的（LEN [1] *的sizeof（int）的）;    / *递归来处理孩子的子* /
    multi_intersection（N / 2，数组，长度的buf [0]）;
    multi_intersection（正 -  N / 2，数组+ N / 2，长度+ N / 2，的buf [1]）;    / *结合孩子的解决方案* /
    交点（BUF [0]，buf中[1]，LEN，出）;    免费（BUF [0]）;
    免费（BUF [1]）;
}
 

类似code作品 multi_union（），但是缓冲长度需要不同计算：工会的结果可能是作为和大的输入的大小，而不是输入的最小尺寸。这也许可以改写少做缓冲区分配。另外，递归可以改写使用迭代，以同样的方式归并可以写入使用迭代，但目前的递归方法只使用O（log n）的额外堆栈空间呢。

I have those functions which are making intersection/union but just of two arrays. I need too improve them to work with n-arrays: arr = {{1,2,3},{1,5,6},...,{1,9}}.
The arrays are sorted , and their elements are unique among them.
Example (intersection):
Input: {{1,2,3,4},{2,5,4},{4,7,8}}
Output: {4}

arr1[],arr2 - arrays
m,n - length of the arrays Intersection function:

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++;
    }
  }
}

and union 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), and the same goes for intersection(). I.e. you can decompose the union or intersection of n sets into n unions or intersections of 2 sets (as NuclearGhost points out in a comment on the question). What you need to do is change your current functions so that they build up a resulting set, instead of immediately printing the result. You can then make a separate function that prints a set.

For efficiency, you want to take the union or intersection of sets that are roughly of equal size. So a divide-and-conquer approach should work alright, assuming that all input sets are likely to be of roughly equal size.

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

Similar code works for multi_union(), except that the buffer lengths need to be calculated differently: the result of a union could be as large as the sum of the sizes of the inputs, rather than the minimum size of the inputs. It could probably be rewritten to do less buffer allocation. Also the recursion could be rewritten to use iteration, the same way mergesort can be written to use iteration, but the current recursive approach uses only O(log n) additional stack space anyway.

这篇关于交，并用C正阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！