Leetcode每日一题 —— 1722. 执行交换操作后的最小汉明距离

1722. 执行交换操作后的最小汉明距离 - 力扣（LeetCode）

1722. 执行交换操作后的最小汉明距离 - 给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。 相同长度的两个数组 source 和 target 间的 汉明距离...

思路

注意 allowedSwaps 中所有下标对应的元素是可以进行任意次交换的。如果把 allowedSwaps 视作边列表，下标视作顶点，输入就可以建模成一个无向图。

很明显这个无向图的一个连通块对应 source 和 target 的一组元素下标，一个连通块（一组）内的元素是可以任意重新排列的。

• 提到连通块就可以想到用并查集了。

因此问题就转换为了统计每个组内，source 和 target 对应的不同的元素数量 diffCnt，所有组的 diffCnt 累加起来就是最终的最小汉明距离结果。

• 注意，allowedSwaps 可能为空，最差的情况下可以按每个下标自成一组来处理。

咱代码主要就按着上面这个思路写的，比较暴力，但好像真能过…可优化空间还超级大！

代码

class UnionFind{
private:
    vector<int> parents;
    vector<int> sizes;
public:
    UnionFind(int n){
        parents.resize(n,-1);
        sizes.resize(n,1);
    }
    int find(int x){
        // 带路径压缩查询
        return parents[x]==-1 ? x : parents[x]=find(parents[x]);
    }
    int merge(int x1, int x2){
        // 启发式合并两棵树，然后返回组号
        int root1=find(x1),root2=find(x2);
        if(root1==root2){
            return root1;
        }
        if(sizes[root1]<sizes[root2]){
            swap(root1,root2);
        }
        parents[root2]=root1;
        sizes[root1]+=sizes[root2];
        return root1;
    }
};

class Solution {
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        // allowedSwaps 中所有下标对应的元素是可以多次交换的
        // 可以把 allowedSwaps 中的下标对视作无向边，每个下标为一个顶点
        // 一个连通块内的下标的数字可以任意组合（因为可以交换任意次）
        // allowedSwaps 相当于把 source 进行了分组，每组内重新排列数字，使得这一组在 source 和 target 间的汉明距最小

        // 因此关键点是维护每个组内的不同元素数量，这个是最难想的，本题还考察到集合操作
        int n=source.size();
        // 组号 -> 元素下标集
        unordered_map<int, unordered_set<int>> sGMap,tGMap;

        UnionFind uf(n);

        // 先扫描 allowedSwaps 加入边，统计每个组内下标对应元素出现次数
        for(vector<int>& as:allowedSwaps){
            // 因为连通过程可能先独立再连起来，这里合并完后再统计
            uf.merge(as[0],as[1]);
        }
        for(vector<int>& as:allowedSwaps){
            int group=uf.merge(as[0],as[1]);
            // source
            sGMap[group].emplace(as[0]);
            sGMap[group].emplace(as[1]);
            // cout<<"PUT "<<as[0]<<", "<<as[1]<<" TO SGROUP "<<group<<endl;
            // target
            tGMap[group].emplace(as[0]);
            tGMap[group].emplace(as[1]);
            // cout<<"PUT "<<as[0]<<", "<<as[1]<<" TO TGROUP "<<group<<endl;
        }

        // 遍历所有的下标 0 到 n-1，统一进行分组
        // 这样既包含了有交换关系的下标，也包含了那些独立不交换的下标
        for(int i = 0; i < n; i++){
            int group = uf.find(i);
            sGMap[group].emplace(i);
            tGMap[group].emplace(i);
        }

        // 处理完成后对比每个组，统计每个组不同的元素数量（组内元素数量 - 交集数量）
        int res=0;
        for(auto it=sGMap.begin();it!=sGMap.end();it++){
            int group=it->first;
            int total=0;
            int intersect=0;
            // 存储 target 组内 元素 -> 出现次数
            // 顺便统计组内总元素数
            unordered_map<int,int> tAMap;
            for(auto sIt=tGMap[group].begin();sIt!=tGMap[group].end();sIt++){
                tAMap[target[*sIt]]++;
                total++;
            }
            // 计算交集元素数量
            for(auto sIt=sGMap[group].begin();sIt!=sGMap[group].end();sIt++){
                int num=source[*sIt];
                if(tAMap.count(num)>0&&tAMap[num]>0){
                    intersect++;
                    tAMap[num]--;
                }
            }
            res+=total-intersect;
        }
        return res;
    }
};

1 个帖子 - 1 位参与者

阅读完整话题