列表中最少的交换元素，使其与另一个列表相同，并在 python 中计算交换

Question

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

注意：两个列表的元素将只有 0 和 1.如果无法通过交换使它们相同，那么我将打印 -1.如果开头相同，我将打印 0，如果它不一样，那么， 我想做一个 == 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

输出：

2

输入：

0 1 0
1 0 0

输出：

1

输入：

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(，则找不到解决方案并返回 -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