如何使用Python中的类生成quickfind算法并返回列表集作为结果

Question

我想使用python类制作一个快速查找算法。我不确定如何返回最终数据集。如果连接变量设置如下，我想返回最终结果：

N = 10
connections = [(4,3), (3,8)]
result = [0,1,2,8,8,5,6,7,8,9]

课程代码为：

class QuickFind(object):
    def __init__(self, N):
        self.lst = list(range(N))

    def union(self, a, b):
        old = self.lst[a]
        new = self.lst[b]
            for ind in self.lst:
            if ind == old:
                self.lst[ind] = new

# execution code is:
for i, j in connections:
    QuickFind(10).union(i, j)

... some code ...

print(result)

Answer 1

您的代码当前正在为connections上循环的每次迭代创建一个QuickFind实例，但随后它会丢弃该对象。如果希望在同一个对象上完成所有union调用，并且希望以后能够看到结果，则需要更改该设置，以便只创建一个对象，并将对该对象的引用存储在变量中

试着这样做：

qf = QuickFind(10)

for i, j in connections:
    qf.union(i, j)

...

result = qf.lst
print(result) # or combine these lines into print(qf.lst)

在union的实现中也存在一个问题。从循环中得到的ind变量的名称有点误导，因为它不是索引，而是列表中的值。在if语句中，您可以正确地将其作为值处理（将其与old进行比较，后者也是值），但在随后的赋值中，您将其用作索引。我认为您确实需要一个值和一个索引，因此我建议重写循环以使用enumerate，这样您就可以在需要时拥有每个循环：

for i, val in enumerate(self.lst):
    if val == old:
        self.lst[i] = new