C++刷LeetCode（1722. 执行交换操作后的最小汉明距离）【并查集】【map】
题目描述：给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps = 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source != target （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。
在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
示例 1：
输入：source = , target = , allowedSwaps = [,]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source =
- 交换下标 2 和 3 指向的元素：source =
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
示例 2：
输入：source = , target = , allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：
输入：source = , target = , allowedSwaps = [,,,]
输出：0
提示：
n == source.length == target.length
1 <= n <= 105
1 <= source, target <= 105
0 <= allowedSwaps.length <= 105
allowedSwaps.length == 2
0 <= ai, bi <= n - 1
ai != bi
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
vector<int>father;
public:
int find_root(int x){
if(x == father)return x;
return find_root(father);
}
void merge(int x, int y){
int temp1 = find_root(x);
int temp2 = find_root(y);
father = temp2;
}
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
//并查集
int len1 = source.size();
int len2 = allowedSwaps.size();
//初始化father
for(int i = 0; i < len1; i++){
father.push_back(i);
}
//合并
for(int i = 0; i < len2; i++){
merge(allowedSwaps, allowedSwaps);
}
//连通分量
map<int, map<int, int> >store1;//用map！！
map<int, map<int, int> >store2;
for(int i = 0; i < len1; i++){
int root = find_root(i);
store1]++;
store2]++;
}
//计算
int res = 0;
for(auto& : store1){
for(auto& : value){
res += min(store1, store2);
}
}
return len1 - res;
}
};
参考链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/5650bing-cha-ji-map-by-cacia-whrw/ 容易超时，用map数据结构降低时间复杂度。
页:
[1]