0

我试图实现一个（天真的）quick_find_union如下

class QF(object):
    def __init__(self,N):
        self.id=[x for x in range(N)]
    def connected(self,p,q):
        assert type(p)==int
        assert type(q)==int
        return self.id[p]==self.id[q]

    def union(self,p,q):
        assert type(p)==int
        assert type(q)==int
        for x in self.id:
            pid=self.id[p]
            qid=self.id[q]
            if x==pid:
                x=qid
#        for i in range(len(self.id)):
#            pid=self.id[p]
#            qid=self.id[q]
#            if self.id[i]==pid:
#                self.id[i]=qid

    def show_array(self):
        print self.id

if __name__=='__main__':
    qf=QF(10)
    qf.show_array()
    print qf.connected(1,4)
    qf.union(1,4)
    qf.show_array()
    print qf.connected(1,4)

这返回

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False

但是当我只使用方法 union 中的注释掉部分时，它按预期工作

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
False
[0, 4, 2, 3, 4, 5, 6, 7, 8, 9]
True

为什么会这样？它与尝试在迭代时修改数组元素有关吗？我对此不是很清楚..有人可以解释一下吗？

4

1 回答 1

0

x=qid只需将名称重新绑定到名称所指x的对象。qid它不会修改self.id列表中的元素。

用于enumerate()获取索引和值，并self.id使用索引更新列表：

for i, x in enumerate(self.id):
    pid=self.id[p]
    qid=self.id[q]
    if x==pid:
        self.id[i]=qid
于 2013-02-06T04:54:27.253 回答