LeetCode 5650. 执行交换操作后的最小汉明距离

亦凉 2024-05-08 06:09 1阅读 0赞

##### 题目链接 #####

[题目链接][Link 1]

##### 思路 #####

怎么想：这道题的意思是给你一个数组，其中数组中的某些数字间可以相互交换，交换次数不限，问经过交换后和目标数组对应位置元素不相同的个数；这里有一个非常巧的点，即只要(0,1)可交换，且(1,2)可交换，那么(0,2)就必然可交换；  
怎么做：我们可以用并查集的方法把可以相互交换的下标放到一个集合（即分支）中，每个分支中的点都是可以相互交换的，这样就会存在多个这样的分支；但是为了根据下标找到其所属的分支，我们还需要一个map，所属分支的根结点作为key，整个分支内的元素作为value；这样就可以在遍历source数组时，根据元素所在的下标判断其所在的分支，并判断当前元素是否在所属分支中；

##### 代码 #####

class Solution {
        
    public:
        vector<int> f;
        int find(int t){
        
            if(f[t] != t)  f[t] = find(f[t]);
            return f[t];
        }
        int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        
            int n = source.size();
            f.resize(n);
            for(int i = 0; i < n; i ++) f[i] = i; //赋初值
            for(auto& ele : allowedSwaps){
        
                int fa = find(ele[0]), fb = find(ele[1]);
                if(fa != fb) f[fb] = fa;//合并集合
            }
            unordered_map<int, unordered_multiset<int>> m;//把下标作为每个set的id
            for(int i = 0; i < n; i ++) m[find(i)].insert(source[i]);//构建map,map会自动把不存在的key加进去
            int res = 0;
            for(int i = 0; i < n; i ++){
        
                auto& e = m[find(i)];//e是一个set
                auto it = e.find(target[i]);//在当前集合set中查找target[i]
                if(it != e.end()) e.erase(it);//如果找到后需要删除，因为可能有重复的
                else res++;
            }
            return res;
        }
    };

##### 总结 #####

1、如果用递归的方式写find函数，可以直接压缩路径；  
2、map\[key\]可以在没有相应关键字时加上相应关键字；

[Link 1]: https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/