前言

        欢迎大家积极在评论区留言发表自己的看法，知无不言，言无不尽，养成每天刷题的习惯，也可以自己发布优质的解题报告，供社区一同鉴赏，吸引一波自己的核心粉丝。
        今天是六月集训第二十六天：并查集

一、练习题目

        1559. 二维网格图中探测环
        1391. 检查网格中是否存在有效路径
        1202. 交换字符串中的元素

二、算法思路

1.并查集原理

还在学并查集。

1.1并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。
1.2并查集通常包含两种操作

• 查找(Find)：查询两个元素是否在同一个集合中
• 合并(Union)：把两个不相交的集合合并为一个集合

2.适用说明

并查集用在一些N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。

3.并查集的基本数据表示

如上图 0-4 下面都是 0，5-9 下面都是 1，表示 0、1、2、3、4 这五个元素是相连接的，5、6、7、8、9 这五个元素是相连的。

4.并查集C++初始化实现

const int MAXN = 300010;
int fset[MAXN];

void init(int n) {
    // 初始化每一个，fset[i]指向自己，没有涉及到合并的操作。
    for (int i = 0; i < n; ++i) {
        fset[i] = i;
    }
}
1
2
3
4
5
6
7
8
9

现在每个结点各自为王，所以自己就是自己的老大，所以Parent数组指向的就是自己本身。

5.并查集查找C++实现

O(1)的时间复杂度，查询元素所在的集合编号

// 查询根结点
int find(int x){
    if(Parent[x]==x)
        return x;
    else
        return find(Parent[x]);
}
1
2
3
4
5
6
7

查找自己的老大是谁，用递归的方法实现对集合中的代表元素(老大)的查询：一层一层访问双亲结点，直至根结点（根结点的标志就是根结点本身）。要判断两个元素是否属于同一个集合，只需要看它们的根结点是否相同即可，即看他们的老大是否是同一个人。

例如查找鬼灯水月的老大是谁？

通过递归查找，先查找数组下标为2的元素，为1，所以他自己不是自己的老大，他的老大是1号，也就是佐助
接下来看看佐助的老大是谁，查看数组下标为1的元素，为0，所以佐助也不是自己的老大，佐助的老大是0号，也就是鸣人
接下来看看鸣人的老大是谁，查看数组下标为0的元素，为0，所以鸣人自己就是老大，所以递归结束，这个集合的老大为0号。

6.并查集的合并C++实现

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        for (int i = 1; i <= n; ++i) {
            if (fset[i] == rx) {
                fset[i] = ry;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10

• 1、1559. 二维网格图中探测环：
• 2、1391. 检查网格中是否存在有效路径：
• 3、1202. 交换字符串中的元素：

三、源码剖析

// 1559. 二维网格图中探测环
class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size(), ans = -1, premin = nums[0]; //(1)
        for(int i = 1; i < n; i++) {
            if (nums[i] > premin) {
                ans = max(ans, nums[i] - premin); //(2)
            } else
                premin = min(premin, nums[i]); //(3)
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 1、前缀最小值初始成数组的第一个数;
• 2、如果发现右边存在一个数比premin大那就相减并，将ans更新成比较大的值,最终要返回是最大的差值也就是ans；
• 3、如果发现num[i]比维护的前缀最小值小的话，把premin更新成nums[i]。

// 1391. 检查网格中是否存在有效路径
class Solution {
public:
    int findClosestNumber(vector<int>& nums) {
        int n = nums.size(), ans = nums[0];
        for(auto num : nums) {
            if (abs(num) == abs(ans)) //(1)
                ans = max(ans, num);
            else if (abs(num) < abs(ans)) { //(2)
                ans = num;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 1、绝对值相等那ans保存数值更大的那个；
• 2、绝对值不等而且是小的情况下，ans就更新为更小的数值。

// 1202. 交换字符串中的元素
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans = prices; //(1)
        for(int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    ans[i] = (prices[i] - prices[j]); //(2)
                    break;
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 1、