Pla*_*sma 2 algorithm disjoint-sets data-structures
这是我即将进行的测试的练习题中的一个问题。我希望得到帮助，找到更有效的解决方案来解决这个问题。现在，我知道我可以通过使用 3 个简单的for循环来解决此类问题，但那就是O(N^3).
此外，我相信以某种方式合并二分搜索将是最好的方法，并给我O(log n)我正在寻找的答案。不幸的是，我有点卡住了。
三向集合不相交问题定义如下：给定三个项目集合A、B和C，如果所有三个集合没有共同元素，则它们是三向不相交的，即不存在x使得x在A、B和C中。
假设A、B、 C是可订购的商品集合（整数）；此外，假设可以在 O( n log n ) 时间内对n 个整数进行排序。给出一个 O( n log n ) 算法来判断集合是否是三向集合不相交。
感谢您的帮助
问题陈述已经给出了如何解决问题的明显提示。假设这 3 个集合是数学集合（每个集合中的元素都是唯一的），只需将 3 个集合混合在一起并排序，然后线性遍历列表并搜索是否存在相同项目的 3 个实例。时间复杂度以排序为主，为O(n log n)。辅助空间复杂度最多为O(n)。
另一种解决方案是使用基于哈希的映射/字典。只需计算 3 组中项目出现的频率即可。如果任何项目的频率等于 3（可以在检索频率进行更新时检查），则这 3 个集合不是 3 路不相交的。插入、访问和修改可以以摊余复杂度完成O(1)，因此时间复杂度为O(n)。空间复杂度也是O(n)。