题目

给你两个整数数组 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

思路

做1722. 执行交换操作后的最小汉明距离 - 图1时看到有说是这个题的简单版本，就顺便来做一下这个题。

1722. 执行交换操作后的最小汉明距离 - 图2是需要将同一连通分量按字母顺序排列，这个题是需要对比1722. 执行交换操作后的最小汉明距离 - 图3和1722. 执行交换操作后的最小汉明距离 - 图4数字的次数，如果完全一致，就可以在交换顺序后达到最小的汉明距离。如果有不同的数字，那么就会增加汉明距离。因此，和1202不同的是，对于每一个连通分量代表元，我们统计1722. 执行交换操作后的最小汉明距离 - 图5中各个数字的次数，然后遍历1722. 执行交换操作后的最小汉明距离 - 图6去和1722. 执行交换操作后的最小汉明距离 - 图7进行比对，具体的实现细节见代码注释。

代码

  1. class Solution {
  2.     public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
  3.         int n = source.length;
  4.         UnionFind uf = new UnionFind(n);
  5.         for (int[] swap : allowedSwaps) {
  6.             uf.union(swap[0], swap[1]);
  7.         }
  8.         // 统计target中，每个连通分量中各个数字出现的次数
  9.         // key为连通分量代表元，value为一个哈希表，存放连通分量各个数字出现的次数
  10.         Map<Integer, Map<Integer, Integer>> t = new HashMap<>();
  11.         for (int i = 0; i < n; i++) {
  12.             Map<Integer, Integer> map = t.computeIfAbsent(uf.find(i), k -> new HashMap<>());
  13.             map.put(target[i], map.getOrDefault(target[i], 0) + 1);
  14.         }
  15.         int diff = 0;
  16.         // 可以将target看做"标答"，现在检验source有多符合标答
  17.         // 当然也可以像上面统计target一样，统计好source每个连通分量中各个数字出现的次数，这里省略了一个map
  18.         for (int i = 0; i < n; i++) {
  19.             Map<Integer, Integer> map = t.get(uf.find(i));
  20.             // source[i]在target中不一定存在，所以用了getOrDefault
  21.             int cnt = map.getOrDefault(source[i], 0);
  22.             // source[i]在target中找到了，将target中的次数减一
  23.             if (cnt > 0) {
  24.                 map.put(source[i], cnt - 1);
  25.             } else {
  26.                 // 没找到，就产生了一个汉明距离
  27.                 diff++;
  28.             }
  29.         }
  30.         return diff;
  31.     }
  32. }
  34. class UnionFind {
  35.     int[] parent;
  37.     public UnionFind(int n) {
  38.         parent = new int[n];
  39.         for (int i = 0; i < n; ++i) {
  40.             parent[i] = i;
  41.         }
  42.     }
  44.     public int find(int p) {
  45.         while (parent[p] != p) {
  46.             parent[p] = parent[parent[p]];
  47.             p = parent[p];
  48.         }
  49.         return p;
  50.     }
  52.     public void union(int p, int q) {
  53.         int proot = find(p);
  54.         int qroot = find(q);
  55.         if (proot == qroot) return;
  56.         parent[proot] = qroot;
  57.     }
  58. }

也可以使用两个map记录分别记录1722. 执行交换操作后的最小汉明距离 - 图8和1722. 执行交换操作后的最小汉明距离 - 图9中每个连通分量中各个数字出现的次数，最后做比较计算结果。

  1. class Solution {
  2.     public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
  3.         int n = source.length;
  4.         UnionFind uf = new UnionFind(n);
  5.         for (int[] swap : allowedSwaps) {
  6.             uf.union(swap[0], swap[1]);
  7.         }
  8.         Map<Integer, Map<Integer, Integer>> s = new HashMap<>();
  9.         for (int i = 0; i < n; i++) {
  10.             Map<Integer, Integer> map = s.computeIfAbsent(uf.find(i), k -> new HashMap<>());
  11.             map.put(source[i], map.getOrDefault(source[i], 0) + 1);
  12.         }
  13.         Map<Integer, Map<Integer, Integer>> t = new HashMap<>();
  14.         for (int i = 0; i < n; i++) {
  15.             Map<Integer, Integer> map = t.computeIfAbsent(uf.find(i), k -> new HashMap<>());
  16.             map.put(target[i], map.getOrDefault(target[i], 0) + 1);
  17.         }
  18.         int ans = 0;
  19.         for (Map.Entry<Integer, Map<Integer, Integer>> entry : s.entrySet()) {
  20.             int deputy = entry.getKey();
  21.             Map<Integer, Integer> num2Cnt = entry.getValue();
  22.             for (Map.Entry<Integer, Integer> entry1 : num2Cnt.entrySet()) {
  23.                 int num = entry1.getKey();
  24.                 int cnt = entry1.getValue();
  25.                 int diff = cnt - t.get(deputy).getOrDefault(num, 0);
  26.                 if (diff > 0) {
  27.                     ans += diff;
  28.                 }
  29.             }
  30.         }
  31.         return ans;
  32.     }
  33. }
  35. class UnionFind {
  36.     int[] parent;
  38.     public UnionFind(int n) {
  39.         parent = new int[n];
  40.         for (int i = 0; i < n; ++i) {
  41.             parent[i] = i;
  42.         }
  43.     }
  45.     public int find(int p) {
  46.         while (parent[p] != p) {
  47.             parent[p] = parent[parent[p]];
  48.             p = parent[p];
  49.         }
  50.         return p;
  51.     }
  53.     public void union(int p, int q) {
  54.         int proot = find(p);
  55.         int qroot = find(q);
  56.         if (proot == qroot) return;
  57.         parent[proot] = qroot;
  58.     }
  59. }