并查集操作一般步骤：
-
并查集模版套上
-
构建映射关系<root节点，集合>
-
执行相关操作，得到题目结果
看到题目后，首先我的做法是：
- 将allowedSwaps分成可以互相交换的集合，比如[[0,1],[2,3]]，分成两个集合[0,1]和[2,3]
- 对每个集合对应的下表排序， 因为一个集合中的下标是可以随便排列的，souce=[1,2,3,4]每个集合子集排序后是[1,2,3,4]，target每个子集排序后是[1,2,4,5]
- 然后比较每个位置不同数字个数，为1
其中第一步，我使用了递归，超时.....，又使用了广度遍历，超时......，其实我也发现了这个问题，就是存在大量的重复计算，但是却又无能为力?
最后，看了题解，发现是使用并查集...........
题解：
class Solution {private class UnionFind{// 节点的祖先节点private int []parent;// 节点的高度，开始时随机选一个做父亲，父亲的高度越来越高，就变成祖先了private int []rank;// 初始化，自己是自己的祖先public UnionFind(int n){this.parent = new int[n];this.rank = new int[n];for(int i=0; i<n; i++){this.parent[i] = i;this.rank[i] = 1;}}// 高度高的是祖先，合并public void union(int x, int y){int rootX = find(x);int rootY = find(y);if(rootX == rootY){return;}if(rank[rootX] == rank[rootY]){parent[rootX] = rootY;rank[rootY]++;}else if(rank[rootX] < rank[rootY]){parent[rootX] = rootY;}else {parent[rootY] = rootX;}}// 找祖先public int find(int x){if(x != parent[x]){parent[x] = find(parent[x]);}return parent[x];}}public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {int res = 0;// 如果不交换if(allowedSwaps.length == 0){for(int i=0; i<source.length; i++){if(source[i] != target[i]){res++;}}return res;}// 第一步，将任意交换结点对输入并查集int len = source.length;UnionFind unionFind = new UnionFind(len);for(int allowedSwap[]: allowedSwaps){int index1 = allowedSwap[0];int index2 = allowedSwap[1];unionFind.union(index1, index2);}// 第二步，构建映射关系 <祖先节点，<可交换的值，出现次数>>Map<Integer, Map<Integer, Integer>> hashMap = new HashMap<>(len);for(int i=0; i<len; i++){// 节点的祖先int root = unionFind.find(i);// 同一个祖先的节点，对应同一个集合if(hashMap.containsKey(root)){Map<Integer, Integer> map = hashMap.get(root);if(map.containsKey(source[i])) {map.put(source[i], map.get(source[i]) + 1);}else {map.put(source[i], 1);}}else {hashMap.computeIfAbsent(root, key -> new HashMap<>()).put(source[i], 1);}}// 第三步，执行详细操作for(int i=0; i<source.length; i++){// 找到祖先节点int root = unionFind.find(i);// 找到祖先对应的集合，也就是当前可交换的元素及出现次数Map<Integer, Integer> map = hashMap.get(root);// 如果存在可交换的，则执行map更新if(map.containsKey(target[i])) {int nums = map.get(target[i]);if(nums == 1) {map.remove(target[i]);}else {map.put(target[i], nums-1);}// 如果不存在，则res++}else {res++;}}return res;}
}第二步：