当集合不相交时，是否有任何与联合查找相似的交集查找算法？

Question

我想找到包含整数值的集合的交集？ 如果说你有4-5个2k-4k整数列表，最有效的方法是什么？

Answer 1

如果你有记忆腾出：

• 创建一组，将持有的每个值的出现次数的数量。
• 对于每一个整数我在每个组，增加我
• 提取整数的出现次数的多少与一些OCCURENCES等于套数的

这是理论上的O（总和所有集合基数+检索）

其中retrieveal可以是您的整数范围（如果您使用原始数组）或您的集合的联合的基数（如果您使用散列表来枚举定义发生的值）。

如果你的集合的边界是已知的而且很小，你可以用一个足够大的整数的简单数组来实现它（通常是256位的8位字符）。

否则，你需要某种散列表，理论上它应该在o（n）中。

Answer 2

在许多语言中，例如C++集合被实现为平衡二叉树，因此您可以直接在O(NlogM)中评估集合交集，只需查看O(logM)中的其他集合即可。

优化： -

当你想为多套，你可以做到这一点是huffman coding使用的优化： -

1. 使用的集的优先级队列，其选择最小的一套第一个
2. 选择两个最小集合首先评估交集并将其添加到队列中。
3. 这样做，直到你得到空的交集或剩下一组（交集）。

注：使用std ::设置如果用C++