查找交集

Question

我們給出n組不同大小的整數。每個集合也可以包含重複。我必須找到交集。如果一個元素在所有集合中出現多次，它應該被添加到結果中。

例如，考慮有三組{0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6}。所述給定集合的交集應該是{3,5,5}

我的做法是：

1.Sort陣列。

2.比較從最小數組開始的每個元素並更新計數。

是否有更有效的方法來找到交集？

Answer 1

如果你的「套」只包含小整數，然後它們可以通過計數組成的數組來表示...例如，{5,2,3,5,6}是

index 0 1 2 3 4 5 6 
count 0 0 1 1 0 2 1 

這種集合的交集被計數的分鐘：

 index 0 1 2 3 4 5 6 
      ------------- 
{0,5,5,3,4} 1 0 0 1 1 2 0 
{5,2,3,5,6} 0 0 1 1 0 2 1 
{1,3,5,5,6} 0 1 0 1 0 2 1 
min   0 0 0 1 0 2 0 = {3,5,5} 

如果這些值不是小整數，但它們很少，只需保留一個值的數組 - 它用作值和小整數（它們是數組的索引）之間的映射。

如果有太多的值使得每個集合的計數數組過於昂貴，則使用從值到計數的映射來表示每個「集合」，以及值的數組......然後迭代該數組生成每個值，迭代地圖以獲取計數並計算其最小值。爲此，您需要一個哈希表或二叉樹庫來實現這些映射......或者使用比C更多的現代語言中的任何一種，當然這些語言都提供這樣的集合類型。

Answer 2

例如，您可以爲每個數組創建一個字典，遍歷每個數組添加到他們的計數器，並添加到「全局」字典中是否檢測到新數字。然後，您從「全球」字典中選擇下一個數字（至少在一個櫃檯詞典中保證存在），然後您至少獲得所有計數器。當然，如果您在單個字典中遇到空字符，則不會將此數字添加到結果中。否則，向結果數組中添加「最小找到」數量的「數字」。有了這樣的字典結構，算法的完整複雜度約爲O(n*m)其中M是您的集合的最大尺寸，N是它們的數量，而如果您對集合進行排序，則複雜度爲O(n*m*log(m))，如果您的集合包含每個元素超過1000個。

Answer 3

這裏是我的代碼，編譯在C99（不要忘記實現獲取，插入，刪除功能第一）：

struct MyNode { MyNode * next; int value; int frequency; } 

// returns MyNode pointer when value exist 
MyNode * get(MyNode * head, int val); 

// insert a new value, with frequency = 1 
void insert(MyNode * head, int val); 

// remove an element from the linked-list 
bool remove(MyNode * head, int val); 

int * intersection (int ** set, int w, int * h) 
{ 
    MyNode * head = 0; 
    MyNode * temp = 0; 
    int finalSize = 0; 
    int k = 0; 

    for (int i=0; i<w; i++) 
    { 
     for (int j=0; j<h[i]; j++) 
     { 
      temp = get(head, set[i][j]); 

      if (temp == 0) 
      { 
       insert(head, set[i][j]); 
       finalSize++; 
      } 
      else 
      { 
       temp->frequency++; 
      } 
     } 
    } 

    temp = head; 
    while (temp != 0) 
    { 
     if (temp->frequency != w) 
     { 
      temp = temp->next; 
      remove(head, temp->value); 
      finalSize--; 
     } 
     else 
      temp = temp->next; 
    } 

    int * intersection = (int*)malloc(finalSize*sizeof(int)); 

    temp = head; 
    while (temp != 0) 
    { 
     intersection[k++] = temp->data; 
     temp = temp->next; 
    } 

    return intersection; 
} 

Answer 4

我建議你的解決方案的唯一優化是將你的數組（它們不是真正的集合，因爲它們有重複項）轉換爲鍵值字典，這樣鍵將是數組的元素，值會是發生次數。對於您的測試示例：{0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6}這些字典看起來像那樣

{0->1, 3-<1, 4->1, 5->2} 
{2->1, 3->1, 5->2, 6->1} 
{1->1, 3->1, 5->2, 6->1} 

然後，比較從最小字典開始的字典對，如果元素同時出現在兩個字段中 - 則採用較少的字典數。 這種優化將節省處理重複所需的時間。你可以將其轉換回數組。