[TOC]

For two arraies `nums1` and `nums2`, Hanming distance indicates how many elements in these two arraies are different.

Formally, it is the number of indices `i` for `0 <= i <= n-1` where `nums1[i] != nums2[i]`

**Examples:**

>>> a = [1,2,2]

>>> b = [1,1,2]

>>> HanmingDistance(a,b)

>>> a = [1,2,2]

>>> b = [2,1,4]

>>> HanmingDistance(a,b)

|2021/01/10|WC223_03|[Minimize Hamming Distance After Swap Operations](https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/)| M | [Python](https://github.com/codename1995/leetcodehub/blob/master/python/WC223_03_Minimize_Hamming_Distance_After_Swap_Operations.py) 并查集典型应用|

||WC223_01|[Decode xored array](https://leetcode-cn.com/problems/decode-xored-array/) |E| a xor b = c </br> 异或的逆运算： </br> Python: a = - ( ~(c xor b) + 1)

|WC223 |1394/3870 |36.0%|

import math

import collections

class Solution:

def minimumHammingDistance(self, source, target, allowedSwaps):

# 参考大佬解法：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/python3-bing-cha-ji-ha-xi-biao-by-yim-6-4a03/

n = len(source)

parent = {i:i for i in range(n)}

# 定义并查集寻根算法

def find(x):

if x!=parent[x]:

parent[x] = find(parent[x])

return parent[x]

# 进行连通

for x,y in allowedSwaps:

rootX, rootY = find(x), find(y)

if rootX!=rootY:

parent[rootY] = rootX

# 统计连通结果

dic = collections.defaultdict(list)

for i in range(n):

root = find(i)

dic[root].append(i)

res = 0

for k,v in dic.items():

a = [source[i] for i in v]

b = [target[i] for i in v]

Counter = collections.Counter(b)

for c in a:

if Counter[c]:

Counter[c] -= 1

else:

res += 1

return res

import time

start = time.clock()

source = [1,2,3,4]

target = [2,1,4,5]

allowedSwaps = [[0,1],[2,3]]

ExpectOutput = 1

solu = Solution() # 先对类初始化，才能进行调用

temp = solu.minimumHammingDistance(source, target, allowedSwaps)

if (temp == ExpectOutput):

print('right')

else:

print('wrong')

print(temp)

elapsed = (time.clock() - start)

print("Time used:", elapsed)