Идентификация "похожих списков" для вызова CodeFights

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

Решение, основанное на ответе @Prune. Оно выполняется менее чем за 4 секунды, но, возможно, вы можете написать лучше

def areSimilar (a,b):
    counter=0
    ind1=[]
    ind2=[]
    if len(a) == len(b):
        for i in range(len(a)):
            if a[i] != b[i]:
                counter+=1
                ind1.append(a[i])
                ind2.append(b[i])
                if counter == 2:
                    if ind1[0] == ind2[1] and ind1[1] == ind2[0]:
                        flag= True
                    else:
                        flag = False
    else:
        flag= False

    if counter == 0:
        flag= True
    elif counter ==1 or counter > 2:
        flag=False
    return flag

Answer 2

Это не очень компактно, но работает.

Поскольку вы проверяете, чтобы точное положение было одинаковым (с максимальным обменом 1), вы можете использовать один и тот же цикл.

Я заставил приведенный ниже код немедленно возвращаться, если не выполняются определенные условия, такие как длина массива и если массив даже содержит те же элементы (исключая позицию). Затем цикл for проверяет положение и пытается 1 обменять 2 элемента. Положение заменяемого элемента должно быть больше, чем в предыдущем тестировании, поскольку мы не хотим повторно тестировать элемент.

def areSimilar(a, b):

    flag = False
    swap = False
    if len(a) is not len(b):
        return False

    arrlen = len(a)
    if set(a) == set(b):
        pos1 = None
        pos2 = None
        for i in range(arrlen):
            if a[i] == b[i]:
                flag = True
            else:
                if pos1 is None:
                    if swap is False:
                       swap = True
                       pos1 = i
                       pos2 = b.index(a[i])
                       if pos2 > i:
                           flag = True
                    else:
                        return False
                else:
                    if b[pos1] == a[i]:
                        flag = True
                    else:
                        return 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]
print(areSimilar(a,b))

Answer 3

Простая итерация по двум спискам для подсчета количества различий.

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]))

Это выводит:

True
True
False

Answer 4

Вы можете попробовать это: -

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 5

Да, ваша логика мучительно медленная. Нет смысла использовать вложенные циклы: вы превратили задачу O (N) в программу O (N ^ 2) .

Во-первых, списки могут быть похожими, только если они имеют одинаковую длину. После того, как вы это проверите, пройдите парные списки один раз , отметив позиции, где элементы не совпадают. Если вы найдете третье несоответствие, они не похожи. Если вы дойдете до конца с одним несоответствием, они не похожи. Если вы обнаружите 0 несоответствий, они похожи.

Единственный случай, когда возникнут дополнительные трудности, это если вы нашли точно две позиции, где элементы не совпадают. Назовите их i и j. На этом этапе просто проверьте, является ли a[i] == b[j] and a[j] == b[i]. Вернуть результат этого сравнения.

Обратите внимание, что нигде во время этого процесса вы на самом деле не меняете элементы. Вам не нужно делать списки идентичными, вам просто нужно определить, возможно ли это со свопом 0 или 1.