给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个
allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（ 下标从 0 开始
）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （ 下标从 0 开始 ）的下标 i（0 <= i <= n-1）的数量。
在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
示例 1：
**输入：** source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
**输出：** 1
**解释：** source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [ **2** , **1** ,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1, **4** , **3** ]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
示例 2：
**输入：** source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
**输出：** 2
**解释：** 不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：
**输入：** source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
**输出：** 0
提示：
n == source.length == target.length1 <= n <= 1051 <= source[i], target[i] <= 1050 <= allowedSwaps.length <= 105allowedSwaps[i].length == 20 <= ai, bi <= n - 1ai != bi
解法
思路和算法
对于长度为 n 的数组 source 和 target，以及可以交换元素的下标对数组 allowedSwaps，可以将下标和可以交换元素的下标对看成图，每个下标是图中的结点，每个可以交换元素的下标对是图中的边，则数组 allowedSwaps 中的每一对可以交换元素的下标对应两个下标在图中的同一个连通分量。
如果两个下标可以通过一条边或多条边相连，则两个下标在图中的同一个连通分量，一定可以经过一次或多次交换操作实现这两个下标处的元素的交换。如果两个下标在图中的不同连通分量，则无法通过交换操作实现这两个下标处的元素下标。为了计算经过任意次交换操作之后的数组 source 和 target 的最小汉明距离，应分别计算每个连通分量在经过任意次交换操作之后的最小汉明距离。
连通性问题可以使用并查集解决。并查集初始化时，n 个下标分别属于 n 个不同的集合。初始化之后，遍历数组 allowedSwaps，将每一对可以交换元素的下标合并到同一个集合，遍历所有可以交换元素的下标对之后，得到所有下标组成的连通分量。
根据所有下标组成的连通分量，分别计算每个连通分量中的数组 source 和 target 的元素差异，根据元素差异计算最小汉明距离。对于每个 0 \le i < n，遍历数组 source 和 target，执行如下操作。
得到下标 i 所在连通分量的根，记为 root。
使用哈希表记录连通分量 root 中的每个元素的计数。将 source}[i] 在哈希表中的计数加 1，将 target}[i] 在哈希表中的计数减 1。由于最小汉明距离需要根据数组 source 和 target 的元素差异计算，因此数组 source 中的每个元素的计数为正，数组 target 中的每个元素的计数为负，可以实现同一个连通分量的两个数组中的相同元素抵消。
遍历两个数组之后，即可得到每个连通分量中的数组 source 和 target 的元素差异。用 totalDifference 表示元素差异总数，初始时 totalDifference} = 0，遍历每个连通分量对应的哈希表，对于哈希表中的每个元素，将该元素对应的计数的绝对值加到 totalDifference。
遍历结束之后，totalDifference 即为所有连通分量的元素差异总数之和。由于每个下标处的元素差异对应数组 source 的一个计数 1 和数组 target 的一个计数 -1，因此 totalDifference 为最小汉明距离的两倍，最小汉明距离为 \Big\lfloor \dfrac{\textit{totalDifference} }{2} \Big\rfloor。
代码
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
UnionFind uf = new UnionFind(n);
for (int[] swap : allowedSwaps) {
uf.union(swap[0], swap[1]);
}
Map<Integer, Map<Integer, Integer>> allGroupElements = new HashMap<Integer, Map<Integer, Integer>>();
for (int i = 0; i < n; i++) {
int root = uf.find(i);
allGroupElements.putIfAbsent(root, new HashMap<Integer, Integer>());
Map<Integer, Integer> groupElements = allGroupElements.get(root);
groupElements.put(source[i], groupElements.getOrDefault(source[i], 0) + 1);
groupElements.put(target[i], groupElements.getOrDefault(target[i], 0) - 1);
}
int totalDifference = 0;
Set<Map.Entry<Integer, Map<Integer, Integer>>> entries = allGroupElements.entrySet();
for (Map.Entry<Integer, Map<Integer, Integer>> entry : entries) {
Map<Integer, Integer> groupElements = entry.getValue();
Set<Map.Entry<Integer, Integer>> group = groupElements.entrySet();
for (Map.Entry<Integer, Integer> groupEntry : group) {
int count = groupEntry.getValue();
totalDifference += Math.abs(count);
}
}
return totalDifference / 2;
}
}
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
rank = new int[n];
}
public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx]++;
}
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class Solution {
public int MinimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.Length;
UnionFind uf = new UnionFind(n);
foreach (int[] swap in allowedSwaps) {
uf.Union(swap[0], swap[1]);
}
IDictionary<int, IDictionary<int, int>> allGroupElements = new Dictionary<int, IDictionary<int, int>>();
for (int i = 0; i < n; i++) {
int root = uf.Find(i);
allGroupElements.TryAdd(root, new Dictionary<int, int>());
IDictionary<int, int> groupElements = allGroupElements[root];
groupElements.TryAdd(source[i], 0);
groupElements[source[i]]++;
groupElements.TryAdd(target[i], 0);
groupElements[target[i]]--;
}
int totalDifference = 0;
foreach (KeyValuePair<int, IDictionary<int, int>> pair in allGroupElements) {
IDictionary<int, int> groupElements = pair.Value;
foreach (KeyValuePair<int, int> group in groupElements) {
int count = group.Value;
totalDifference += Math.Abs(count);
}
}
return totalDifference / 2;
}
}
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
rank = new int[n];
}
public void Union(int x, int y) {
int rootx = Find(x);
int rooty = Find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx]++;
}
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
}
|
复杂度分析
时间复杂度：O((n + m) \times \alpha(n))，其中 n 是数组 source 和 target 的长度，m 是数组 allowedSwaps 的长度，\alpha 是反阿克曼函数。并查集的初始化需要 O(n) 的时间，这里的并查集使用了路径压缩和按秩合并，遍历数组 allowedSwaps 执行合并操作需要 O(m \times \alpha(n)) 的时间，遍历数组 source 和 target 执行查找操作需要 O(n \times \alpha(n)) 的时间，因此时间复杂度是 O((n + m) \times \alpha(n))。
空间复杂度：O(n)，其中 n 是数组 source 和 target 的长度。并查集需要 O(n) 的空间。
