三向设置不相交

Question

这是我即将进行的测试的练习问题。我希望得到帮助，找到一个更有效的解决方案来解决这个问题。现在，我知道我可以通过使用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）算法来确定这些集是否是三向设置不相交的。

谢谢你的帮助

Answer 1

问题陈述给出了如何解决问题的明显暗示。假设3组是数学集（元素在每组中是唯一的），只需将3组混合在一起并对它们进行排序，然后线性遍历列表并搜索是否有3个相同项的实例。时间的复杂性主要是排序，即O(n log n)。辅助空间的复杂性至多是O(n)。

另一种解决方案是使用基于散列的地图/字典。只计算3套物品的频率。如果任何项目的频率等于3（这可以在检索频率以进行更新时进行检查），则3组不是3路不相交的。插入，访问和修改可以在O(1)摊销的复杂性中完成，因此时间复杂度是O(n)。空间复杂性也是O(n)。

Answer 2

如果复杂性是约束（并且空间或常数都不是），则可以在O（n）中求解。创建两个位图，将整数从A映射到第一个，将整数从B映射到第二个。然后遍历第三个（C）直到你耗尽，或者你找到一个条目，其中bitmapA（testInt）和bitmapB（testInt）都被设置。

Answer 3

我们可以用o（n）来解决这个问题。如果我们使用Set数据结构并考虑初始容量和load factor，这是可能的。

public static boolean checkThreeWaySetDisjointness(Set<Integer> a, Set<Integer> b, Set<Integer> c)
    {
        int capacity = Math.round((a.size() + b.size()) / 0.75f) + 1;
        Set<Integer> container = new HashSet<Integer>(capacity);
        container.addAll(a);
        for (int element : b)
        {
            if (!container.add(element))
            {
                if (c.contains(element))
                {
                    return false;
                }
            }
        }
        return true;
    }

我们正在创建新的Set容器，因为如果我们开始直接在任何现有的Set a / b / c中添加，一旦达到其实际大小的75％的容量，内部java将创建新的Hashset并复制其中的整个现有Set。这种开销将具有O（n）的复杂性。因此，我们在这里创建了大小容量的新HashSet，这将确保不会有复制的开销。然后复制整个Set a，然后继续从Set b中逐个添加元素。在Java中，如果add（）返回false，则表示当前集合中已存在元素。如果是，请在第三个集合c中检查相同内容。添加和包含HashSet的方法具有O（1）的复杂性，因此整个代码在O（n）中运行。