2

交差/結合を行っている関数がありますが、2つの配列だけです。n-arrays: 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 に答える