intersection et union de n-tableaux en C

J’ai ces fonctions qui font l’intersection / union mais juste de deux tableaux. J’ai également besoin de les améliorer pour pouvoir utiliser des tableaux n: ar = {{1,2,3}, {1,5,6}, …, {1,9}}.
Les tableaux sont sortingés et leurs éléments sont uniques parmi eux.
Exemple (intersection):
Entrée: {{1,2,3,4}, {2,5,4}, {4,7,8}}
Sortie: {4}

arr1 [], arr2 – tableaux
m, n – longueur des tableaux Fonction d’intersection:

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

et fonction syndicale:

 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) , il en va de même pour intersection() . En d’autres termes, vous pouvez décomposer l’union ou l’intersection de n ensembles en n unions ou intersections de 2 ensembles (comme le souligne NuclearGhost dans un commentaire sur la question). Ce que vous devez faire, c’est modifier vos fonctions actuelles pour qu’elles créent un ensemble résultant, au lieu d’imprimer immédiatement le résultat. Vous pouvez ensuite créer une fonction distincte qui imprime un jeu.

Pour plus d’efficacité, vous voulez prendre l’union ou l’intersection d’ensembles approximativement de taille égale. Par conséquent, une approche diviser pour mieux régner devrait fonctionner correctement, en supposant que tous les ensembles d’entrées auront probablement une taille à peu près égale.

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

Un code similaire fonctionne pour multi_union() , sauf que les longueurs de mémoire tampon doivent être calculées différemment: le résultat d'une union pourrait être aussi grand que la sum des tailles des entrées, plutôt que la taille minimale des entrées. Il pourrait probablement être réécrit pour faire moins d’allocation de mémoire tampon. De plus, la récursion pourrait être réécrite pour utiliser l'itération, de la même manière que mergesort pour utiliser l'itération, mais l'approche récursive actuelle utilise uniquement un espace de stack supplémentaire O (log n).

présumer que la valeur maximale dans les tableaux est inférieure à K. N est le nombre de tableaux

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