โปรแกรมลด Hamming Distance หลังสลับได้ใน Python

มีอาร์เรย์ src, tgt ความยาวเท่ากัน และ allowedSwaps คู่ดัชนีที่สลับได้ไม่จำกัดครั้ง หา Hamming distance น้อยที่สุดหลังสลับใน src ได้อย่างไรก็ตาม

ตัวอย่าง: src=[2,3,4,5], tgt=[3,2,5,6], allowedSwaps=[[0,1],[2,3]] ผลลัพธ์ 1

วิธีแก้ปัญหา (Union-Find + Counter)

1. Union-Find รวมดัชนีที่สลับได้เป็นกลุ่ม (connected components)
2. ในแต่ละกลุ่ม นับความถี่ค่าใน src และ tgt
3. Hamming distance ของกลุ่ม = sum(|count_src[c] - count_tgt[c]|) / 2
4. รวมทุกกลุ่ม

ตัวอย่างโค้ด

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)):
        groups[find(i)].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