为代码战Challenge定义“相似列表”

Question

如果通过交换其中一个列表中最多一对元素，可以从另一个列表中获取一个列表，则两个列表称为相似列表。我解决了这个问题，但是我需要让它在4秒钟内运行（Python3）所有的输入。有什么办法可以提高效率吗？在

def areSimilar (a,b):
    counter=0
    for i in range(len(a)):
        for j in range(len(b)):
            if counter < 1 and a[i]!=b[i]:
                if a[i]==b[j]:
                    temp=b[j]
                    b[j]=b[i]
                    b[i]=temp
                    counter+=1
                else:
                    flag=False

    if a == b:
        flag=True
    else:
        flag = False

    return flag

a= [832, 998, 148, 570, 533, 561, 894, 147, 455, 279]
b= [832, 998, 148, 570, 533, 561, 455, 147, 894, 279]
p=areSimilar(a,b)

我认为嵌套循环是我的问题。在

Answer 1

你可以试试这：在

def areSimilar(a,b):
    if len(a)<2 or len(b)<2:
        return 'Wrong input'
    if len(a) != len(b):
        return False
    if len(a) == len(b) == 2:
        if (a[0] != b[0] and a[0] != b[1]) or (a[1] != b[0] or a[0] != b[1]):
            return False
        else: return True
    var = 0
    for i, j in zip(a,b):
            if i!=j:
                    var += 1
            if var > 2:
                    return False
    if var != 2:
        return False
    return True

>>> a= [832, 998, 148, 570, 533, 561, 894, 147, 455, 279]
>>> b= [832, 998, 148, 570, 533, 561, 455, 147, 894, 279]
>>> areSimilar(a,b)
True

Answer 2

简单地迭代两个列表来计算差异的数量就可以了。在

import operator
from itertools import zip_longest
def areSimilar(a, b):
    if a == b:
        return True
    diff = list(filter(lambda t: operator.ne(*t), zip_longest(a, b)))
    return len(diff) == 2 and diff[0] == diff[1][::-1]
a= [832, 998, 148, 570, 533, 561, 894, 147, 455, 279]
b= [832, 998, 148, 570, 533, 561, 455, 147, 894, 279]
print(areSimilar(a, b))
print(areSimilar([0, 1], [0, 1]))
print(areSimilar([0, 1], [2, 3]))

该输出：

^{pr2}$

Answer 3

是的，你的逻辑太慢了。没有理由使用嵌套循环：您已经将O（N）问题变成了O（N^2）程序。在

首先，列表只有在长度相同的情况下才能相似。一旦你检查过了，检查一下成对列表一次，注意元素不匹配的位置。如果你发现第三个不匹配，它们就不相似了。如果你到最后一个不匹配，他们是不相似的。如果你发现0个不匹配，它们是相似的。在

唯一一个更困难的情况是，如果你找到了两个元素不匹配的位置。称它们为i和j。此时，只需检查a[i] == b[j] and a[j] == b[i]。返回比较结果。在

请注意，在这个过程中，无处实际上您是在交换元素。您不需要使列表完全相同，您只需确定是否可以使用0或1交换。在