# P1722 给你两个整数数组 `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：** ```plain text 输入：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：** ```plain text 输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [] 输出：2 解释：不能对 source 执行交换操作。 source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。 ``` **示例 3：** ```plain text 输入：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 <= 105` - `1 <= source[i], target[i] <= 105` - `0 <= allowedSwaps.length <= 105` - `allowedSwaps[i].length == 2` - `0 <= ai, bi <= n - 1` - `ai != bi` # 总体思路：每个可交换的索引是可以**任意且无限次数**交换的，故联想到并查集。题目转换为：在所有连通块当中（用并查集构建的根节点来遍历每个联通快），其联通块内部不同的元素个数有几个（每个元素只能用一次）。先根据题目给的allowedswaps来构建连通块。构建完成后以每个连通块的根节点（用find寻找当前索引的根节点）来作为外层map的key（索引），内层map的key用来记录sources[当前索引]的值，vaule记录当前元素的个数。之后对target进行遍历，用find寻找当前索引的根节点。进入这个联通快查找是否有相同的元素，如果没有，答案加一（无相同元素）。如果有，对此元素在map当中记录的个数减一（找到相同元素）。 ```c++ class Solution { public: vectorfa; vectorrank;//按秩合并 int find(int x){ return x == fa[x] ? x : find(fa[x]); } void merge(int x, int y){ x = find(x); y = find(y); if(x == y)return; if(rank[x] < rank[y]){ swap(x, y); } fa[y] = x; if(rank[x] == rank[y])rank[x]++; } int minimumHammingDistance(vector& source, vector& target, vector>& allowedSwaps) { int n = target.size(); fa.resize(n); rank.resize(n, 1); for(int i = 0; i < n; i++)fa[i] = i; for(auto e : allowedSwaps){ merge(e[0], e[1]); } unordered_map>sets; for(int i = 0; i < n; i++){ int f = find(i); sets[f][source[i]]++; } int ans = 0; for(int i = 0; i < n; i++){ int f = find(i); if(sets[f][target[i]] > 0)sets[f][target[i]]--; else ans++; } return ans; } }; ``` # 反思：好多天没刷。复习了并查集，学习了二维map。