Минимальное количество элементов обмена в списке, чтобы он был таким же, как другой список, и подсчет обмена в python

Question

Я должен указать в качестве ввода a = [0,1,0,1] и b = [1,0,1,0]

Примечание: элементы обоих списков будут просто 0 и 1. если невозможно сделать их одинаковыми с помощью обмена, я напечатаю -1. Если это то же самое в начале, я напечатаю 0, и если это не то же самое, то я хочу сделать a == b, в этом случае , мне нужно 2 минимальных свопа. 1-й своп будет, 0-й индекс a и 1-й индекс a и 2-й своп будет, 2-й индекс a и 3-й индекс a. После этого a будет таким же, как b.

Вот мой код:

def xx(a,b):
    move = 0
    if a == b:
        print(0)
    else:
        if len(a) == 1 and len(a) == len(b):
            print(-1)
        else:
            for i in range(len(a)):
                if a[i] != b[i]:
                    j = a.index(b[i])
                    a[i] = a[j]
                    move += 1
            count_swap = move // 2
            print(count_swap)
a = list(map(int,input().split()))
b = list(map(int,input().split()))
xx(a,b)

Есть ли эффективный способ получить количество свопов?

Введите:

0 1 0 1
1 0 1 0

Выход:

2

Вход:

0 1 0
1 0 0

Выход:

1

Вход:

0
1

Выход :

-1

Answer 1

Это должно быть решение O (N), которое выполняет итерацию по элементам и выполняет замену в списке b. Если мы выйдем за конец списка b (IndexError), решение не будет найдено и вернем -1.

def count_swaps(a, b):
    swaps = 0
    for idx in range(len(a)):
        if a[idx] != b[idx]:
            try:
                b[idx], b[idx + 1] = b[idx + 1], b[idx]
                swaps += 1
            except IndexError:
                return -1

    return swaps


assert count_swaps([0, 1, 0, 1], [1, 0, 1, 0]) == 2
assert count_swaps([0, 1, 0], [1, 0, 0]) == 1
assert count_swaps([0], [1]) == -1

Answer 2

Во-первых, для того, чтобы свопы делали списки равными, они должны начинаться с одинакового количества единиц и нулей. Таким образом, мы можем использовать Counter для проверки на невозможность.

И, во-вторых, один своп обязательно исправляет два различия. Таким образом, мы можем просто подсчитать разницу и разделить на 2. На самом деле нам не нужно выполнять какие-либо обмены.

Демонстрация:

from collections import Counter

def swap_count(xs, ys):
    if xs == ys:
        return 0
    else:
        cx = Counter(xs)
        cy = Counter(ys)
        if cx == cy:
            n_diffs = sum(x != y for x, y in zip(xs, ys))
            return n_diffs // 2
        else:
            return -1

def main():
    tests = [
        (2, [0, 1, 0, 1], [1, 0, 1, 0]),
        (1, [0, 1, 0], [1, 0, 0]),
        (-1, [0], [1]),
        (0, [0, 1, 0, 1], [0, 1, 0, 1]),
    ]
    for exp, xs, ys in tests:
        n = swap_count(xs, ys)
        print(n == exp, n, xs, ys)

main()

Вывод:

True 2 [0, 1, 0, 1] [1, 0, 1, 0]
True 1 [0, 1, 0] [1, 0, 0]
True -1 [0] [1]
True 0 [0, 1, 0, 1] [0, 1, 0, 1]