找到一对没有交叉的对

Question

给定一组n对整数,有一种快速的方法来确定是否存在两对(x ₁,y ₁)和(x ₂,y ₂),以便集合{x ₁,y ₁ } 的交集并且{x ₂,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)额外的存储器.

希望这可以帮助!