在 Python 中交换操作后最小化汉明距离的程序
假设我们有两个整数数组，src和tgt，它们的长度相同。我们还有一个数组allowedSwaps，其中allowedSwaps[i]包含一对(ai,bi)表示我们可以将索引ai处的元素与数组src的元素索引bi交换。（我们可以按任意顺序根据需要多次交换特定索引对处的元素）。正如我们所知，两个长度相同的数组src和tgt的汉明距离是元素不同的位置数。在对数组src执行任意数量的交换操作后，我们必须找到src和tgt的最小汉明距离。
所以，如果输入像src=[2,3,4,5],tgt=[3,2,5,6],allowedSwaps=[[0,1],[2,3]]，那么输出将是1因为src可以通过以下方式转换：交换索引0和1，所以源=[3,2,4,5]，交换索引2和3，所以源=[3,2,5,4].这里src和tgt的汉明距离为1，因为它们在1个位置不同：索引3。
示例
让我们看看以下实现以获得更好的理解-
from collections import defaultdict, Counter
def solve(src, tgt, allowedSwaps):
graph = [ n for n in range(len(src)) ]
def find(x):
while graph[x] != x:
graph[x] = graph[graph[x]]
x = graph[x]
return x
def union(x, y):
x1, y1 = find(x), find(y)
graph[x1] = y1
for x, y in allowedSwaps:
union(x,y)
groups = defaultdict(list)
for i in range(len(src)):
i1 = find(i)
groups[i1].append(i)
ans = 0
for ids in groups.values():
counter = Counter()
for idx in ids:
counter[src[idx]] += 1
counter[tgt[idx]] -= 1
ans += sum( abs(val) for val in counter.values())/2
return ans
src = [2,3,4,5]
tgt = [3,2,5,6]
allowedSwaps = [[0,1],[2,3]]
print(solve(src, tgt, allowedSwaps))输入
[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]输出结果
1