leetcode 1722. Minimize Hamming Distance After Swap Operations

Problem: 1722. 执行交换操作后的最小汉明距离

既然可以两两交换数字，而且次数不限制，所以可以任意排列

首先并查集拿到所有可能的聚合体，然后对每个根节点，拿到这个树的所有索引i，以及这个树的索引对应数值的统计值

然后遍历每颗树，对当前索引i，若target[l[i]]在ump2内，且值>0则-1，否则sum++，标记target[l[i]] = -1

最后统计不能交换且不同的个数

Code

class joinarr { public: vector<int> arr; int n; joinarr(int n) { this->n = n; arr.resize(n); for(int i = 0; i < n; i++) arr[i] = i; } int find(int a) { while(a!=arr[a]) a = arr[a]; return a; } void join(int a, int c) { int aa = find(a); int cc = find(c); if(aa < cc) arr[cc] = aa; else arr[aa] = cc; } }; class Solution { public: int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) { int n = source.size(); int m = allowedSwaps.size(); joinarr ja = joinarr(n); for(int i = 0; i < m; i++) { ja.join(allowedSwaps[i][0], allowedSwaps[i][1]); } unordered_map<int, vector<int>> ump; unordered_map<int, unordered_map<int, int>> ump2; int ind; for(int i = 0; i < n; i++) { ind = ja.find(i); ump[ind].push_back(i); ump2[ind][source[i]]++; } int num, sum = 0; for(auto&& [k, l] : ump) { for(int i = 0; i < l.size(); i++) { num = target[l[i]]; if(ump2[k].count(num) > 0 && ump2[k][num] > 0) { ump2[k][num]--; } else { sum++; } target[l[i]] = -1; } } for(int i = 0; i < n; i++) { if(target[i] >= 0 && target[i] != source[i]) { sum++; } } return sum; } };