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

发布时间：2020-12-20 11:32:54 所属栏目：Python 来源：网络整理

导读：给定一组n对整数,有一种快速的方法来确定是否存在两对(x1,y1)和(x2,y2),以便集合{x1,y1}和{x2,x2}的交集是空的？例如,{(0,1),(0,2),(2,(3,2)}具有{(0,2)}作为答案.然而{(0,1)}没有这样的对. 在Python中,您可以按如下方式尝试所有对. l = [(0,2)]print [pair

给定一组n对整数,有一种快速的方法来确定是否存在两对(x1,y1)和(x2,y2),以便集合{x1,y1}和{x2,x2}的交集是空的？

例如,{(0,1),(0,2),(2,(3,2)}具有{(0,2)}作为答案.然而{(0,1)}没有这样的对.

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

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

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

解决方法

在阅读本文之前阅读 templatetypedef answer.

因为他完成了所有的工作,所以我会亲自追捕那些赞成这个答案的人,而不会给出他的回答

这是templatetypedef answer中定义的算法的一个(不言自明的)python实现：

def exists_pair(seq):
    if len(seq) < 2:
        return False
    a,b = seq[0]  # could be: seq.pop() if modifications are allowed
    a_group = set()
    b_group = set()
    for c,d in seq:
        if not ({a,b} & {c,d}):
            return True
        elif {a,b} == {c,d}:
            continue
        elif a in {c,d}:
            a_group.add(c if c != a else d)
        else:
            b_group.add(c if c != b else d)

    if not a_group:
        return False

    # b_group - a_group: elements of b_group that do not appear in a_group
    return bool(b_group - a_group)

无需检查空b_group,因为b_group – a_group的结果始终是b_group的子集.如果b_group为空,则结果将始终为空,并且空集的布尔值为False,这是正确的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!