交叉點和C中的n數組的聯合

我有那些交叉/聯合但只是兩個數組的函數。我也需要改進它們以使用n數組：arr = {{1,2,3}，{1,5,6}，...，{1,9}}。
數組是排序的，它們的元素在它們之間是唯一的。
實施例（交集）：
輸入：{{1,2,3,4}，{2,5,4}，{4,7,8}}
輸出：{4}交叉點和C中的n數組的聯合

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

來源

2012-11-06 Nicolae Rotaru

的數目這是否： - http://stackoverflow.com/questions/8890154/looking-for-fast-sorted -integer-array-intersection-union-algorithms-implemented幫助？ –

爲什麼不循環使用解決方案-so-far數組和下一個數組調用任何函數的n個數組。 –

union(a, b, c) = union(union(a, b), c)，intersection()也是如此。即你可以將n組的聯合或交集分解爲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()，除了緩衝區長度需要以不同的方式計算：工會的結果可能是作爲輸入的大小之和爲大，而不是的最小尺寸投入。它可能會被重寫爲減少緩衝區分配。此外，遞歸可以被重寫爲使用迭代，就像mergesort可以被寫入使用迭代一樣，但是當前的遞歸方法無論如何都只使用O（log n）額外的棧空間。

來源

2012-11-06 15:25:00

假定在陣列中的最大值爲小於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-06 15:32:32 hankym

交叉點和C中的n數組的聯合

回答

相關問題