2

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

感谢您的帮助

4

3 回答 3

5

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

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

于 2013-03-04T05:56:51.443 回答
2

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

于 2013-03-04T02:22:31.313 回答
1

我们可以用 o(n) 来解决这个问题。如果我们使用 Set 数据结构并考虑初始容量和负载因子，这是可能的。

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，这将确保不会产生复制开销。然后复制整个集合 a，然后继续从集合 b 中一个接一个地添加元素。在 Java 中，如果 add() 返回 false 意味着元素已经存在于当前集合中。如果是，只需在第三组 c 中检查是否相同。HashSet 的方法 add 和 contains 的复杂度为 O(1)，因此整个代码在 O(n) 中运行。

于 2017-12-24T07:17:50.670 回答