Minimize Hamming Distance After Swap Operations

给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数.

这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        DSU dsu = new DSU(n);
        Map<Integer,HashMap<Integer, Integer>> map = new HashMap<>();
        for(int[] a : allowedSwaps){
            dsu.union(a[0], a[1]); 
        }
        for(int i = 0 ; i < n; i++) {
            int d = dsu.get(i);
            map.putIfAbsent(d, new HashMap<Integer, Integer>());
            map.get(d).putIfAbsent(source[i], 0);
            map.get(d).put(source[i], map.get(d).get(source[i]) + 1);
        }
        int res = 0;
        for(int i = 0; i < target.length; i++) { 
            int d = dsu.get(i);
            if(!map.containsKey(d)){ // 如果dsu里没有坐标i (不能swap)
                res++;
            } 
            if(!map.get(d).containsKey(target[i])){ // 如果dsu有, 但是swap里没有target数组需要的
                res++;
            }
            else{
                map.get(dsu.get(i)).put(target[i], map.get(dsu.get(i)).get(target[i]) - 1); // 选了后减少
                if(map.get(dsu.get(i)).get(target[i]) < 0)
                    res++;
            }
        }
        return res;
    }
    private static class DSU {
        private int[] ranks;
        private int[] parents;
        public DSU(int size) {
            this.ranks = new int[size];
            Arrays.fill(ranks, 1);
            this.parents = new int[size];
            for(int i = 0; i < size; i++){
                this.parents[i]= i;
            }
        }

        int get(int v) {
            if (v == parents[v]) return v;
            return parents[v] = get(parents[v]);
        }

        boolean union(int a, int b) {
            a = get(a);
            b = get(b);

            if (a == b) return false;

            if (ranks[a] < ranks[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            parents[b] = a;
            if (ranks[a] == ranks[b]) ++ranks[a];
            return true;
        }
    } 
}