列表中的最小交换元素以使其与另一个列表相同并计算 [=s10=] 中的交换

Question

我必须列出我的输入， a = [0,1,0,1] 和 b = [1,0,1,0]

注意：两个列表的元素都只是 0 并且 1.If 不可能通过交换使它们相同然后我将打印 -1.If 它在开始时相同我将打印 0如果不一样的话，我想做 a == b，在这种情况下，我需要 2 个最小交换。第一次交换将是 a 的第 0 个索引和 a 的第一个索引和第二次交换将是 a 的第二个索引和 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

输出：

输入：

0 1 0
1 0 0

输出：

输入：

0
1

输出：

-1

Answer 1

首先，为了使列表相等，它们必须以相同数量的 1 和 0 开头。所以我们可以用一个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]

Answer 2

这应该是一个复杂度为 O(N) 的解决方案，它遍历项目并对列表 b 执行交换。如果我们离开列表 b (IndexError) 的末尾，则无法找到解决方案并且 return -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

列表中的最小交换元素以使其与另一个列表相同并计算 [=s10=] 中的交换

Minimum swaping elements in a list to make it same like another list and count the swap in python

python

list

compare-and-swap

python-3.x