我有x个集合，每个集合中有y个元素（未排序的整数）。我想找到这些集合中任意一对交集的最大大小。
例如：
*5个集合，大小为3
集合1：12 3
集合2：42 3
集合3：5 6 7
集合4：5 8 9
集合5：5 10 11
最大交集是集合1和集合2，大小为2；答案是2。
因此，可以使用 HashSets 在 O(x^2*y) 的时间复杂度内完成，只需查找所有组合并计算它们的交集大小即可。但我想更快地解决问题。我认为有特定的算法或数据结构可以帮助。你能给我一些想法吗？
更新：x和y约为10^3，元素为整数。而且没有相同的集合。
我能想到的一种优化方法是记住第一个集合与其余集合之间的交集大小，并使用这些数据来减少一些情况。
如何使用它：
如果您有长度为 n 的集合 A、B、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 ]
当你比较第一个元素后，计算intersection(S1,S2)。
(S1[0]=4 != S2[0]=5)
你可以说intersection(S1,S2) <= 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是每个集合中元素的数量：
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)之间。
我想不出一种能够改进 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)))。
set 1: 1 3 2和set 2: 4 2 3，即集合内元素的顺序不重要，那么1和2会相交吗？ - igon