【LeetCode】十七、并查集：岛屿数量
文章目录
1、并查集Union Find
并查集，一种树形的数据结构，处理不相交的两个集合的合并、查询、连通性问题。
引用上面文章的经典解释并查集：
- 一个集合就像一个江湖门派，他们有一个教主（代表元），集合中每个元素只需要记住自己的上级，而不是教主
- find即查询某个元素的代表元（教主）
- union即把两个门派（集合），合并成一个，认一个教主
例子：
查find(x)
有个数组array，长度为10，若array[1] = 6，说明1号元素的上级是6号元素。array[6] = 6，说明6号元素的上级是6号元素，即6号是教主。并查集的查：find(x)，即找x元素的教主
public int find(int x ) {
// 如果x位置的值，等于x，说明x就是教主
if (x == array[x]) {
return array[x];
}
// 如果不是，查x位置的值的上级
return find(array[x]);
}
也可不用递归：
public int find(int x ) {
while(x != array[x]) {
// 查x位置的元素自己的上级
x = array[x];
}
return x;
}
并union(x,y)
两个集合合并，或者说两个门派合并，看似改动很大，其实只要让一个门派的教主给另一个门派的教主当上级即可。因为只关注两个集合的连通性。
// 传入两个门派的元素
public void union(int x, int y) {
//查教主
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// 让Y门派的教主当X门派教主的上级
array[rootX] = rootY;
}
}
如下树形，
对应的数组：数组索引代表元素，数组的值，代表这个位置的元素的上级
合并后，比如让第一个集合的教主做合并后新集合的教主：5号的上级不再是自己，变成了1
2、并查集find的优化：路径压缩 Quick find
用开头引用文章的形象例子，现在要做的就是，防止树形结构过于深，导致查询效率变低，将结果压缩成，只要查一次，就能知道教主是谁：
总之一句话，防止树太高，期待右边，而不是左边
想实现这个效果，可以：查询到x元素的根节点（教主）后，直接将x元素的上级改成根节点。
public int QuickFind(int x ) {
// 如果x位置的值，等于x，说明x就是教主
if (x == array[x]) {
return array[x];
}
// 如果不是，查x位置的值的上级，等递归回退的时候，把x的上级改成根节点
return array[x] = find(array[x]);
}
也就是说，第一次find元素x，是没有压缩路径的，第二次才是优化后的效果
3、并查集union的优化：权重标记
和find优化属于同一思想，union两个集合时，防止树过高，比如合并：
如果这么连，树过高：
比较两棵树的高度，左边为2，右边为3，因此，高的树原地不动，继续做老大，低的树靠过去，union后的效果：
核心思想：
整体代码如下，带权重的union参考：
public class UnionFind {
const int N=1005//指定并查集所能包含元素的个数（由题意决定）
int pre[N]; //存储每个结点的前驱结点的数组
int rank[N]; //树的高度，权重
void init(int n) { //初始化函数，对录入的 n个结点进行初始化
for(int i = 0; i < n; i++){
pre[i] = i; //每个结点的上级都是自己
rank[i] = 1; //每个结点构成的树的高度为 1
}
}
int find(int x) {
//查找结点 x的根结点
if (pre[x] == x) {
return x ;//递归出口：x的上级为 x本身，则 x为根结点
}
return find(pre[x]); //递归查找
}
int findQucik(int x) { //改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低
if (pre[x] == x) {
return x;//递归出口：x的上级为 x本身，即 x为根结点
}
return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx
}
bool isSame(int x, int y) { //判断两个结点是否连通
return find(x) == find(y); //判断两个结点的根结点（即代表元）是否相同
}
void union(int x,int y) {
int rootx = find(x);//寻找 x的代表元
int rooty = find(y);//寻找 y的代表元
if(rootx != rooty) {//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并
if(rank[rootx] > rank[rooty]) {//如果 x的高度大于 y，则令 y的上级为 x
pre[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
pre[rootx] = rooty;//让 x的上级为 y
} else {
pre[rooty] = rootx;
rank[rootx] += 1;//如果 x的高度和 y的高度相同，则令 y的高度加1
}
}
}
}
4、leetcode200：岛屿数量
关于题目的理解，1为陆地，0为水，二维网格外都是水两个示例中的陆地如下：
解法一：DFS
以示例二来分析，从二维网格的第一个元素开始遍历，找到1后，将其改为0（同化），并将其水平或竖直方向上相邻的1也改为0，如下
递归，将找到的1 的 水平或竖直方向上相邻的1 的 水平或竖直方向上相邻的1 再次改为0，结果result + 1，如下：
继续往下遍历，找到了第二个1（说明这又是一块新的岛屿，因为前面同化时，没有把它变成0，即它和前一块岛屿不挨着） ，继续将其同化成0，并递归把其水平或竖直方向上相邻的1也全都改为0，结果result + 1：
继续往下遍历，找到了第三个1，又是一块新的岛屿，继续同化成0，递归把其水平或竖直方向上相邻的1也全都改为0，结果result + 1
继续遍历，没1了，结束，最终result为3。代码实现：
public class P200 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
// 行数
int row = grid.length;
// 列数
int col = grid[0].length;
// 岛屿数量
int result = 0;
// 遍历二维网格
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
// 遇到1，岛屿数量加一，并同化周边陆地
result = result + 1;
// 深度优先，改这个1水平竖直方向上的非0数值
dfs(grid, i, j, row, col);
}
}
}
return result;
}
public static void dfs(char[][] grid, int x, int y, int row, int col) {
// 终止条件：出界或者水平、竖直方向上遇到了0（水域）
if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0') {
return;
}
// 同化
grid[x][y] = '0';
// 上下左右四个方位
dfs(grid, x + 1, y, row, col);
dfs(grid, x - 1, y, row, col);
dfs(grid, x, y + 1, row, col);
dfs(grid, x, y - 1, row, col);
}
}
DFS同化点（x, y）的上下左右四个位置的点：
核心是：找到1后，检查其上下左右四个点是否为1，再检查其上下左右的上下左右，直到出界或者遇到了水域
解法二：BFS
遍历二维网格，遇到1，入队，出队然后把其水平或竖直方向上相邻的1入队，并都同化成0，注意，不再像深度优先一样套娃（把1 的 水平或竖直方向上相邻的1 的 水平或竖直方向上相邻的1 再次改为0）。流程如下：
-
遍历二维网格，找到第一个1，坐标（0，0），也就是图中左上角那个
-
将其入队并同化成0
-
出队，并检查其水平或竖直方向上相邻的位置，有1的话，入队并同化成0
-
出队，并检查出队元素的水平或竖直方向上相邻的位置，有1的话，入队并同化成0
- 继续出队，直到队列为空，则岛屿数量 + 1，继续往下遍历二维网格，找到下一个1
- 入队并同化成0，继续往下
总之，总体思路和DFS一样，不同的是，同化其水平竖直方向上的1时，DFS深度优先，一次同化完，BFS则依靠队列的出队入队，每次只处理相邻的1。（DFS是处理相邻的相邻，连坐到都没1了）
public class P200 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
// 行数
int row = grid.length;
// 列数
int col = grid[0].length;
// 岛屿数量
int result = 0;
// 队列
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
queue.add(new int[]{i, j});
grid[i][j] = '0';
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
// 只看这个1的上下左右四个点，如果这四个点有1，则同化成0，并将这个点自身入队
// 队列不空时，while下一轮会处理新入队的点的上下左右四个点
// 如此，while执行完，和前面DFS一口气改完了这块岛屿所有的1是一个效果
if (x + 1 < row && grid[x + 1][y] == '1') {
grid[x + 1][y] = '0';
queue.add(new int[]{x + 1, y});
}
if (x - 1 >= 0 && grid[x - 1][y] == '1') {
grid[x - 1][y] = '0';
queue.add(new int[]{x - 1, y});
}
if (y + 1 < col && grid[x][y + 1] == '1') {
grid[x][y + 1] = '0';
queue.add(new int[]{x, y + 1});
}
if (y - 1 >= 0 && grid[x][y - 1] == '1') {
grid[x][y - 1] = '0';
queue.add(new int[]{x, y - 1});
}
}
// 发现的1的水平竖直方向相邻的1都同化成0了，岛屿数量+1
result = result + 1;
// 继续往下遍历二维网格，找下一个1
}
}
}
return result;
}
}
解法三：并查集Union Find
这题，对岛屿的描述，是其水平或竖直方向上相邻的1即同一块岛屿，这就是个连通性。先看下二维数组和一维数组的转换：
设二维数组有元素[x][y]，且总列数为col，则：
一维数组索引index = x * col + y
x = index / col
y = index % col
将题中的二维数组转成一维数组：
根据并查集的步骤，先初始化数组，刚开始时，array[i] = i，即元素i的上级是i自己
接下来，遍历二维数组，找到1后，检查其上下左右四个点，是不是也是1，是则做Union，让他们有同一个上级，比如左上角（0，0）位置的那个1
union两次后，1和5的上级都变成了0，一维数组变为：
继续往下遍历，找1，第二个1为（0，1），继续检查其上下左右四个点，是不是也是1，是则做Union，如下：
union一次后，6的上级也变成了0，一维数组变为：
继续往下遍历，找到了第三个1，即第二行第一列那个1，但发现这个1已被union，其上级为0，因此，继续往下。
到第三行第三列的那个1时，其对应的一维数组坐标为12，上级为12，检查其上下左右四个点，发现没有1，因此，保持不变，继续往下走
继续往下走，到了最后一行的第四列，又发现1了，检查其上下左右四个点，发现右边有个1，做一次union：
数组变为：
继续往下遍历，二维网格遍历结束，岛屿的数量 = 陆地数 - union的次数，或者说等于总数 - 水域数 - union的次数。（因为union一次，代表有一块陆地和其他岛屿连一起了），最后得出，岛屿数 = 20 - 13 - 2 - 1 - 1 = 3
public class P200 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
// 行数
int row = grid.length;
// 列数
int col = grid[0].length;
// 水域数量初始值为0，以后每遇到一块水域，该值+1
int waters = 0;
UnionFind unionFind = new UnionFind(grid);
// 遍历二维网格
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '0') {
waters++;
} else {
// 是陆地，检查其上下左右四个点，是1则union
if (i + 1 < row && grid[i + 1][j] == '1') {
// 注意这里二维坐标转为一维坐标
unionFind.union((i + 1) * col + j, i * col + j);
}
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
unionFind.union((i - 1) * col + j, i * col + j);
}
if (j + 1 < col && grid[i][j + 1] == '1') {
unionFind.union(i * col + (j + 1), i * col + j);
}
if (j - 1 >= 0 && grid[i][j - 1] == '1') {
unionFind.union(i * col + (j - 1), i * col + j);
}
}
}
}
// count此时为岛屿数 + 水域数
return unionFind.getCount() - waters;
}
}
/**
* 并查集
*/
class UnionFind {
// 一维数组
int[] root;
// 用于计算岛屿的数量
int count = 0;
// 构造函数
UnionFind(char[][] grid) {
// 行数
int row = grid.length;
// 列数
int col = grid[0].length;
// 初始值为总数，即陆地 + 水域的数量，以后每union一次，count就减一
count = row * col;
root = new int[row * col];
// 初始化
for (int i = 0; i < root.length; i++) {
root[i] = i;
}
}
/**
* find+压缩路径优化
* 返回x的祖先
*/
public int find(int x) {
if (x == root[x]) {
return x;
} else {
root[x] = find(root[x]);
return root[x];
}
}
/**
* 合并
*/
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
root[rootX] = rootY;
// union一次了，注意count减一
count--;
}
}
/**
* 获取count的值
* 和并查集的理论无关，纯给这道题加的
*/
public int getCount() {
return this.count;
}
}
原文地址：https://blog.csdn.net/llg___/article/details/140378357
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！