算法leetcode

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

字数统计: 1.5k字   |   阅读时长: 6分
, ,

摘要: 加边过程中动态查询具体连通分量

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章并查集-加边过程中维护具体连通分量中我们了解了用并查集在加边过程中动态查询具体连通分量的原理。

本文我们看一个相关题目：力扣 1722。

$1 题目

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

1
2
3
4
5
6
7
8
9
提示：

n == source.length == target.length
1 <= n <= 1e5
1 <= source[i], target[i] <= 1e5
0 <= allowedSwaps.length <= 1e5
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

示例 1：
输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：

  • 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
  • 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
    source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：
输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：
输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

$2 题解

算法: 并查集

考虑一个 n 节点的图，编号 0 ~ n - 1，n 为 source 和 target 的长度。

allowedSwaps 中的节点对连一条无向边。表示这两个节点对应的下标是可以交换的。

将所有的边都连上后，属于同一连通分量的节点对应的下标都是可以互相交换的；不在同一连通分量的节点对应的下标是不可交换的。

对于特定连通分量，将它们对应的下标在 source 和 target 中对应的元素视为两个数组的元素，问题就简化成了【两个同长度的数组的交集大小，元素可重复】。可以参考题目 350. 两个数组的交集 II。这个问题有排序和哈希表两种做法，在 STL 中也有相关的组件，参考 【STL】有序容器的集合操作

因此整体的算法可以分为两个大步骤：

  1. 求出所有的连通分量
  2. 枚举所有连通分量，解决两个数组的交集的问题

对于第一步，用并查集维护加边的过程，但是需要在加边过程中维护每个代表元对应的连通分量的节点，并增加一个接口 get_cc_list 返回所有连通分量。

【维护每个代表元对应的连通分量】具体的做法是:

  • 增加一个 vector<vector<int>> 变量 _elements，_elements[i] 表示第 i 个代表元的连通分量，保存连通分量各个节点的列表。
  • 增加一个 unordered_set<int> 变量 roots 表示代表元集合
  • 在 merge 过程中增加对 _elements 的操作。
  • get_cc(i) 返回 _elements[i]。
  • get_cc_list() 枚举 roots所有元素，对每个代表元调用 get_cc 将结果插入结果中

对于第二步，这里就用哈希表的方式处理。记录交集的个数。

枚举所有连通分量，累加 match，最后 n - match 为答案。

代码 (C++)

其中并查集部分完全复制 并查集-加边过程中维护具体连通分量 中的代码模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class UnionFindSet {
public:
    UnionFindSet(int n)
    {
        _father = vector<int>(n, -1);
        _rank = vector<int>(n, 0);
        _elements = vector<vector<int>>(n, vector<int>{});
        for(int i = 0; i < n; ++i)
        {
            _elements[i].push_back(i);
            roots.insert(i);
            _father[i] = i;
        }
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y) return;

        if(_rank[x] < _rank[y])
        {
            roots.erase(x);
            _elements[y].insert(_elements[y].end(), _elements[x].begin(), _elements[x].end());
            _father[x] = y;
        }
        else
        {
            roots.erase(y);
            _elements[x].insert(_elements[x].end(), _elements[y].begin(), _elements[y].end());
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    vector<int> get_cc(int x)
    {
        return _elements[_find(x)];
    }

    vector<vector<int>> get_cc_list()
    {
        vector<vector<int>> result;
        for(int x: roots)
        {
            result.push_back(get_cc(x));
        }
        return result;
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<vector<int>> _elements; // 连通分量内的元素
    unordered_set<int> roots;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};

class Solution {
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        UnionFindSet unionfindset(n);
        for(const vector<int> &edge: allowedSwaps)
            unionfindset.merge(edge[0], edge[1]);
        vector<vector<int>> cc_list =  unionfindset.get_cc_list(); // 所有的连通分量
        int match = 0;
        for(const vector<int> &cc: cc_list)
        {
            unordered_map<int, int> cnts;
            for(int i: cc)
                ++cnts[source[i]];
            for(int i: cc)
            {
                if(cnts.count(target[i]) > 0)
                {
                    ++match;
                    --cnts[target[i]];
                    if(cnts[target[i]] == 0)
                        cnts.erase(target[i]);
                }
            }
        }
        return n - match;
    }
};
Share