A.每日一题：1722. 执行交换操作后的最小汉明距离

题目链接1722. 执行交换操作后的最小汉明距离中等算法原理解法并查集DFS75ms击败35.12%时间复杂度O(mn)①建图允许交换的两个下标之间连边②连通分组用 DFS 遍历把互相连通的下标划分为同一组③计数抵消每组内source元素 1target元素 -1数值归零代表数量匹配可以交换对齐④统计多余的累加所有无法抵消数值的绝对值⑤换算答案答案统计的是不同元素的对数两两成对因此除以 2Java代码class Solution { public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) { int nsource.length; //构建无向图邻接表每个下标是一个节点允许交换的两个下标之间连边 ListInteger[] gnew ArrayList[n]; //初始化 Arrays.setAll(g,_-new ArrayList()); //遍历所有允许的交换对给无向图加边 for(int[] e:allowedSwaps){ int ie[0]; int je[1]; g[i].add(j); g[j].add(i); } //vis数组标记下标是否已经被访问过避免重复遍历同一个连通分量 boolean[] visnew boolean[n]; //累计最小汉明距离 int ret0; //遍历每个下标找到所有未访问的连通分量 for(int x0;xn;x){ if(!vis[x]){ //统计当前连通分量内source和target的元素频率差 MapInteger,Integer hashnew HashMap(); //DFS遍历当前连通分量的所有节点统计元素频率差 dfs(x,source,target,g,vis,hash); //计算当前连通分量贡献的汉明距离 for(int c:hash.values()) retMath.abs(c); } } return ret/2; } private void dfs(int x,int[] source,int[] target,ListInteger[] g,boolean[] vis,MapInteger,Integer hash){ vis[x]true; hash.merge(source[x],1,Integer::sum); hash.merge(target[x],-1,Integer::sum); //遍历当前节点的所有邻接点 for(int y:g[x]) if(!vis[y]) dfs(y,source,target,g,vis,hash); } }