algorithm - 当集合不相交时，是否有类似于联合查找的交集查找算法？

Question

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

Answer 1

在许多语言中，例如 c++ 集合被实现为平衡二叉树，因此您可以直接评估 O(NlogM) 中的集合交集，只需查看另一个集合即可将 n 用作较小的集合大小在 O(logM) 中。

优化:-

如果您希望它用于多个集合，您可以进行 huffman 编码 中使用的优化:-

1. Use a priority queue of sets which selects smallest set first
2. select two smallest sets first evaluate intersection and add it to queue.
3. Do this till you get empty intersection set or one set(intersection set) remaining.

注意:如果使用 c++，则使用 std::set