python - 找到一对没有交集的对

Question

给定一组 n 对整数，是否有一种快速的方法来确定是否存在两对 (x₁, y₁) 和 (x₂, y₂) 使得集合 {x₁, y₁} 和 {x _的交集>2, x₂} 为空？

例如，{(0,1), (0,2), (2,1), (3,2)} 有 {(0,1), (3,2)} 作为答案。但是 {(0,1), (0,2), (2,1)} 没有这样的对。

在 Python 中，您可以按如下方式尝试所有对。

l = [(0,1), (0,2), (2,1), (3,2)]
print  [pairs for pairs in itertools.combinations(l, 2)
    if not (set(pairs[0]) & set(pairs[1]))]

这种方法需要 O(n²) 时间。你能得到更接近线性时间的东西吗？

Answer 1

以下算法应该在 O(n) 时间内工作。它基于以下观察:如果你有一对 {a, b}，那么每隔一对

1. 不包括 a 或 b，或者
2. 至少包括 a 或 b 之一。

如果您选择任何集合 {a, b} 并将彼此的集合归入这五个类别之一，请注意，如果您在情况 1 中得到任何东西，那么您就完成了并且您知道存在这样的一对。所以唯一有趣的情况是当所有其他集合都属于情况 2 时。发生这种情况时，我们可以将这两个组称为“A”组和“B”组(对于匹配 a 的集合和匹配 b 的集合)。

一旦你有了A组和B组，你就知道没有两个A组可以是你想要的对，没有两个B组可以是你想要的对，而{a，b}组不能成为你想要的那对的一部分。唯一的选择是，如果你可以从 A 组中取出一些东西并将它与 B 组中的一些东西配对。仅当 A 组中的某些非 A 组件与 B 组中的任何非 B 组件不匹配时才会发生这种情况。您可以在 O(n) 中检查这一点，方法是构建一个包含 A 组的非 A 组件的哈希表，然后检查 B 组的每个元素是否其非 B 组件在哈希集中。

总而言之，算法是

• 选择一对{a, b}。
• 对于彼此的一对 {c, d}:
  • 如果 {a, b} 和 {c, d} 不相交，您就完成了。
  • 否则，如果 {a, b} = {c, d}，则丢弃 {c, d}。
  • 否则，如果 {c, d} 包含 a，则将其放入 A 组；如果包含 b，则将其放入 B 组。
• 如果 A 组或 B 组中有一个为空，则不存在任何对。返回 false。
• 对于 A 组的每个元素，将该对的非 a 组件添加到哈希集中。
• 如果 B 组的任何元素具有不在哈希集中的非 b 组件，则返回 true，否则返回 false。

这会在 O(n) 的时间内运行并使用 O(n) 的额外内存。

希望这对您有所帮助!