n套之间的最大交集

Question

我有x组中有y个元素（未排序的整数）在他们每个人。我想要找到这组对之间最大交集的大小。

例如：

* 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。并没有相等的组合。

Answer 1

我能想到的一种优化方法是记住第一组和其余部分之间的交集大小，然后使用这些数据来减少某些情况。

你如何使用它：

如果你有套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这是最好的结果你到目前为止。

有什么可以进一步改进的是要记住交叉点的更确切的结果，但仍然没有计算所有的结果。

我不知道这是最好的选择。也许存在完全不同的方法。

Answer 2

下面是一些伪代码：

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是各组的元素个数：

1. 插入到val_map是O(X*Y)
2. 创建counts并且每个元件初始化到零是O(X^2)
3. 如果没有交点（每个值只出现一次），则最后一个循环运行时间为O(X*Y)。但是，另一方面，如果有大量交叉点（所有集合都相同），则最后一个循环将在O(X^2*Y)中运行。

因此，根据交叉点的数量，时间复杂度介于O(X*Y + X^2)和O(X^2*Y)之间。

Answer 3

我不认为这会提高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))）。