用 Python 编写程序，在交换操作后最小化汉明距离

pythonserver side programmingprogramming更新于 2025/12/7 16:12:17

假设我们有两个整数数组，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，因此 source = [3,2,4,5]，交换索引 2 和 3，因此 source = [3,2,5,4]。这里 src 和 tgt 的汉明距离为 1，因为它们在 1 个位置上有所不同:索引 3。

为了解决这个问题，我们将遵循以下步骤 −

graph := 一个大小与 src 相同的列表并用 n 填充
定义一个函数 find() 。这将获取 x
当 graph[x] 与 x 不同时，执行
- graph[x] := graph[graph[x]]
- x := graph[x]
返回 x
定义一个函数 union() 。这将获取 x、y
x1 := find(x), y1 := find(y)
graph[x1] := y1
从 main 方法，执行以下操作
对于 allowedSwaps 中的每一对 (x, y)，执行
- union(x, y)
groups := 一个映射，其中值是列表，默认情况下列表为空
对于范围从 0 到 src 大小 - 1 的 i，执行
- i1 := find(i)
- 在 groups[i1] 末尾插入 i
ans := 0
对于组的所有值列表中的每个 id，执行
- counter := 一个空的映射，用于保存计数值
- 对于 ids 中的每个 idx，执行
  - counter[src[idx]] := counter[src[idx]] + 1
  - counter[tgt[idx]] := counter[tgt[idx]] - 1
  - ans := ans + (counter 值列表中所有 var 的所有 val 绝对值之和)/2
返回 ans

示例

让我们看看下面的实现以便更好地理解 −


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