目标
给你两个整数数组 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.length
- 1 <= n <= 10^5
- 1 <= source[i], target[i] <= 10^5
- 0 <= allowedSwaps.length <= 10^5
- allowedSwaps[i].length == 2
- 0 <= ai, bi <= n - 1
- ai != bi
思路
有两个长度相等的数组 source 和 target，另有一个交换数组 allowedSwaps[i] = [ai, bi]，表示可以交换 source[ai] 与 source[bi]。求按照任意顺序交换任意次之后，source 与 target 的最小汉明距离。汉明距离指满足 source[i] != target[i] 的 i 的个数。
记录可以交换的连通元素的频次，然后比较对应位置上 target 的元素，最小的汉明距离就是对应不上的元素个数。
使用并查集记录连通分量，为每一个连通分量维护一个哈希表，记录元素出现的频次。枚举 target，找到所属的连通分量，将对应连通分量的元素频次 -1，如果最终频次小于 0 那么汉明距离 +1。
代码
/**
* @date 2026-04-21 9:12
*/
public class MinimumHammingDistance1722 {
public class UnionFind {
int[] fa;
public UnionFind(int n) {
this.fa = new int[n];
Arrays.setAll(this.fa, i -> i);
}
public int find(int e) {
if (e != fa[e]) {
fa[e] = find(fa[e]);
}
return fa[e];
}
public void merge(int x, int y) {
int a = find(x);
int b = find(y);
if (a < b) {
fa[b] = a;
} else if (a > b) {
fa[a] = b;
}
}
}
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
UnionFind uf = new UnionFind(n);
for (int[] swap : allowedSwaps) {
uf.merge(swap[0], swap[1]);
}
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int c = uf.find(i);
map.putIfAbsent(c, new HashMap<>());
map.get(c).merge(source[i], 1, Integer::sum);
}
int res = 0;
for (int i = 0; i < n; i++) {
int c = uf.find(i);
map.get(c).merge(target[i], -1, Integer::sum);
if (map.get(c).get(target[i]) < 0) {
res++;
}
}
return res;
}
}
性能
