n套之間的最大交集

我有x組中有y個元素（未排序的整數）在他們每個人。我想要找到這組對之間最大交集的大小。n套之間的最大交集

例如：

* 5臺，大小= 3

組1：1

設定2：4

套3：5 6 7

組4：5 8 9

組5：5 10 11

最大交叉點有設置1組2和它的大小是2; 答案是2.

所以，我可以在O（x^2 * y）使用HashSets，只需查看所有對並計算它們的交集大小即可。但我想更快地做到這一點。我認爲有特定的算法或數據結構可以提供幫助。你能給我一些想法嗎？

UPDATE：x和y爲約10^3，元件是INT。並沒有相等的組合。

來源

2015-11-05 rusted

會設置1和2也相交如果'設置1：1 3 2'和'設置2：4 2 3'，即一組中的元素的順序並不重要？ – igon

是訂單無關緊要 – rusted

元素的值是否有限制？怎麼樣的套數 - 你有這個限制嗎？ –

我能想到的一種優化方法是記住第一組和其餘部分之間的交集大小，然後使用這些數據來減少某些情況。

你如何使用它：

如果你有套A，B，長度n的C和

intersection(A,B) = p 
intersection(A,C) = q

然後

intersection(B,C) <= n - abs(p - q)

對於套在你的情況：

S0 = { 1 2 3 } 
S1 = { 4 2 3 } 
S2 = { 5 6 7 }

你計算intersection(S0,S1) = 2並記住結果：

[ i(0,1)=2 ]

然後intersection(S0,S2) = 0，所以

[ i(0,1)=2; i(0,2)=0 ]

當你比較第一要素

(S1[0]=4 != S2[0]=5)

你可以說，經過計算intersection(S1,S2)intersection(S1,S2) <= 2這是最好的結果你到目前爲止。

有什麼可以進一步改進的是要記住交叉點的更確切的結果，但仍然沒有計算所有的結果。

我不知道這是最好的選擇。也許存在完全不同的方法。

來源

2015-11-05 16:53:47 kostek

下面是一些僞代碼：

function max_intersection(vector<vector<int>> sets): 
    hashmap<int, vector<set_id>> val_map; 
    foreach set_id:set in sets: 
     foreach val in set: 
      val_map[val].push_back(set_id); 
    max_count = 0 
    vector<int> counts = vector<int>(size = sets.size() * sets.size(), init_value = 0); 
    foreach val:set_ids in val_map: 
     foreach id_1:set_id_1 in set_ids: 
      foreach id_2:set_id_2 in set_ids where id_2 > id_1: 
       count = ++counts[set_id_1 * sets.size() + set_id_2]; 
       if (count > max_count): 
        max_count = count; 
    return max_count;

所以如果X是組數和Y是各組的元素個數：

插入到val_map是O(X*Y)
創建counts並且每個元件初始化到零是O(X^2)
如果沒有交點（每個值只出現一次），則最後一個循環運行時間爲O(X*Y)。但是，另一方面，如果有大量交叉點（所有集合都相同），則最後一個循環將在O(X^2*Y)中運行。

因此，根據交叉點的數量，時間複雜度介於O(X*Y + X^2)和O(X^2*Y)之間。

來源

2015-11-05 17:04:42 Joel

算法的複雜度爲O（k^2 * y）。 k是包含具體數字的集合的平均數量。 –

我不認爲這會提高O(x*x*y)一個解決方案，但我可以建議的方式，以避免散列和替代預期複雜O(x*x*y)以10^6額外的內存成本具有複雜性O(x*x*y)。看看你提供的約束條件將不會超過10^6個不同的數字。所以我的想法是以下 - 對所有數字進行排序，然後對它們進行唯一標識（刪除重複項）。將1到10^6（或唯一編號的數字）的唯一編號分配給每個數字（使用它們在排序和唯一數組中的順序）。之後，而不是每對哈希映射，使用一個大小10^6的位集。這樣你就會有一定的複雜度O(x*x*y)（因爲我提出的預計算複雜度爲O(x * y *(log(x) + log (y))）。

來源

2015-11-05 17:09:09

由於您已經對所有數字進行排序+唯一，因此您也可以丟棄僅顯示一次的所有數字 - 因爲它們不能位於兩個不同的集合中！不會改變複雜性，但非常便宜，可能會大大降低常數因子（取決於輸入分佈）。 –

是的，我認爲，但我的建議是集中在最壞的情況下，而不是一般情況下 –

複雜性的解決方案是O（X^2），但實際上它是O（X^2 * 10的6次方），是不是？ – rusted

n套之間的最大交集

回答

相關問題