C++刷LeetCode（1722. 执行交换操作后的最小汉明距离）【并查集】【map】

糖逗

题目描述：

1. 给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
   
2. 
   
3. 相同长度的两个数组&#160;source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足&#160;source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。
   
4. 
   
5. 在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
   
6. 
   
7. &#160;
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
    
12. 输出：1
    
13. 解释：source 可以按下述方式转换：
    
14. - 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
    
15. - 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
    
16. source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
    
17. 示例 2：
    
18. 
    
19. 输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
    
20. 输出：2
    
21. 解释：不能对 source 执行交换操作。
    
22. source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
    
23. 示例 3：
    
24. 
    
25. 输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
    
26. 输出：0
    
27. &#160;
    
28. 
    
29. 提示：
    
30. 
    
31. n == source.length == target.length
    
32. 1 <= n <= 105
    
33. 1 <= source[i], target[i] <= 105
    
34. 0 <= allowedSwaps.length <= 105
    
35. allowedSwaps[i].length == 2
    
36. 0 <= ai, bi <= n - 1
    
37. ai != bi
    
38. 
    
39. 来源：力扣（LeetCode）
    
40. 链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations
    
41. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     vector<int>father;
   
4. public:
   
5.     int find_root(int x){
   
6.         if(x == father[x])return x;
   
7.         return find_root(father[x]);
   
8.     }
   
9.     void merge(int x, int y){
   
10.         int temp1 = find_root(x);
    
11.         int temp2 = find_root(y);
    
12.         father[temp1] = temp2;
    
13.     }
    
14. 
    
15.     int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
    
16.         //并查集
    
17.         int len1 = source.size();
    
18.         int len2 = allowedSwaps.size();
    
19.         //初始化father
    
20.         
    
21.         for(int i = 0; i < len1; i++){
    
22.             father.push_back(i);
    
23.         }
    
24.         //合并
    
25.         for(int i = 0; i < len2; i++){
    
26.             merge(allowedSwaps[i][0], allowedSwaps[i][1]);
    
27. 
    
28.         }
    
29.         //连通分量
    
30.         map<int, map<int, int> >store1;//用map！！
    
31.         map<int, map<int, int> >store2;
    
32.         for(int i = 0; i < len1; i++){
    
33.             int root = find_root(i);
    
34.             store1[root][source[i]]++;
    
35.             store2[root][target[i]]++;
    
36.         }
    
37.         //计算
    
38.         int res = 0;
    
39.         for(auto& [k1, value]: store1){
    
40.            for(auto& [k2, v2]: value){
    
41.                res += min(store1[k1][k2], store2[k1][k2]);
    
42.            }
    
43.         }
    
44.         return len1 - res;
    
45.     }
    
46. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -map-by-cacia-whrw/

糖逗

容易超时，用map数据结构降低时间复杂度。