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