Python程式：交換操作後最小化漢明距離

假設我們有兩個整數陣列 src 和 tgt，它們長度相同。我們還有一個數組 allowedSwaps，其中 allowedSwaps[i] 包含一對 (ai, bi)，表示我們可以交換陣列 src 中索引 ai 處的元素與索引 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
  • 從主方法開始，執行以下操作：
  • 對於 allowedSwaps 中的每個對 (x, y)，執行以下操作：
    • union(x, y)
  • groups := 一個對映，其中值是列表，預設情況下列表為空
  • 對於從 0 到 src 大小 - 1 的每個 i，執行以下操作：
    • i1 := find(i)
    • 將 i 插入到 groups[i1] 的末尾
  • ans := 0
  • 對於 groups 所有值的列表中的每個 ids，執行以下操作：
    • counter := 一個空對映，用於儲存計數值
    • 對於 ids 中的每個 idx，執行以下操作：
      • counter[src[idx]] := counter[src[idx]] + 1
      • counter[tgt[idx]] := counter[tgt[idx]] - 1
      • ans := ans + (counter 所有值的絕對值的總和) / 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))

輸入

[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]

輸出

1

更新於: 2021年10月6日

234 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告