Minimize Hamming Distance After Swap Operations
给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数.
这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
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; } } } |