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;
}
}
}