N集最大相交

Question

我有x个集合，每个集合中都有y元素(未排序整数)。我想找出这两个集合之间相交的最大大小。

例如：

*5套，尺寸=3 1:1 2 3 集合2:4 2 3 一套3:5 6 7 一套4:5 8 9 一套5:5 10 11

最大相交集1与集合2，其大小为2；答案为2。

因此，我可以使用HashSets在O(x^2 * y)中完成，只需查找所有对并计算它们的相交大小。但我想快点。我认为有一些具体的算法或数据结构可以提供帮助。你能给我点主意吗？

UPDATE：X和y约为10^3，元素为int。也没有相等的集合。

Answer 1

我能想到的一个优化是记住第一组和其他集合之间的交集大小，然后使用数据来切割一些情况。

如何使用它：

如果设置为A、B、C of length n和

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 ]

当您在比较第一个元素之后计算intersection(S1,S2)

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

您可以说，intersection(S1,S2) <= 2是迄今为止最好的结果。

可以进一步改进的是记住更精确的交叉口结果，但仍然不能计算所有的结果。

我不确定这是不是最好的选择。也许有完全不同的方法来解决这个问题。

Answer 2

下面是一些psuedocode：

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. 如果没有交叉点(每个值正好发生一次)，那么最后一个循环将在time 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)))。