并查集其实可以优化下，如果从左上角遍历，只需要判断下和右就好了，不用再退回去。

光头哥的代码简洁到极致啊

代码是给人读的，不是为了简短

并查集的话没有必要四周扩散吧？只要i和j方向往前一个看一下就可以了吧？

class Solution { int[] dx = { -1, 1, 0, 0 }; int[] dy = { 0, 0, -1, 1 }; public int numIslands(char[][] grid) { if (grid == null || grid.length <= 0) return 0; UnionFind uf = new UnionFind(grid); int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { for (int k = 0; k < 4; k++) { int nextX = i + dx[k]; int nextY = j + dy[k]; if (!(nextX < 0 || nextX >= m || nextY < 0 || nextY >= n)// 判断是否合法的坐标 && grid[nextX][nextY] == '1') { uf.union(i * n + j, nextX * n + nextY); } } } } } return uf.getCount(); } } class UnionFind { private int count = 0; private int[] rank; private int[] parent; public UnionFind(char[][] grid) { int m = grid.length; int n = grid[0].length; rank = new int[m * n]; parent = new int[m * n]; for (int i = 0; i < parent.length; i++) { parent[i] = -1; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { parent[i * n + j] = i * n + j; count++; } } } } private int findRoot(int i) { if (parent[i] != i) parent[i] = findRoot(parent[i]); return parent[i]; } public boolean connected(int p, int q) { return findRoot(p) == findRoot(q); } public void union(int p, int q) { int rootp = findRoot(p); int rootq = findRoot(q); if (rootp != rootq) { if (rank[rootp] > rank[rootq]) { parent[rootq] = rootp; } else if (rank[rootp] < rank[rootq]) { parent[rootp] = rootq; } else { parent[rootq] = rootp; rank[rootp] += 1; } count--; } } public int getCount() { return count; } }

光头哥的代码是错的，输出结果是全部1的数量，他每次去1都返回了一次1

func numIslands(grid [][]byte) int { //参数校验 if len(grid) == 0 { return 0 } n, m := len(grid), len(grid[0]) //定义并初始化并查集 var count int unionSet := make([]int, n * m) for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == '1' { count++ } unionSet[i * m + j] = i * m + j } } u := &unionFindSet{} u.UnionSet = unionSet u.Count = count //只需要处理右下节点 dires := []struct{x, y int}{{1, 0}, {0, 1}} for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == '0' { continue } //判断当前节点周围是否有挨着的1 for _, d := range dires { x := i + d.x y := j + d.y if 0 <= x && x < n && 0 <= y && y < m && grid[x][y] == '1' { u.union(i * m + j, x * m + y) } } } } return u.Count } type unionFindSet struct { UnionSet []int Count int } func (ufs *unionFindSet) union(x, y int) { xRoot := ufs.unionFindRoot(x) yRoot := ufs.unionFindRoot(y) if xRoot != yRoot { ufs.UnionSet[xRoot] = yRoot ufs.Count-- } } func (ufs *unionFindSet) unionFindRoot(k int) int { //根结点的值等于它本身 if ufs.UnionSet[k] != k { ufs.UnionSet[k] = ufs.unionFindRoot(ufs.UnionSet[k]) } return ufs.UnionSet[k] }

func numIslands(grid [][]byte) int { //参数校验 if len(grid) == 0 { return 0 } n, m := len(grid), len(grid[0]) //定义并初始化并查集 var count int unionSet := make([]int, n * m) for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == '1' { count++ } unionSet[i * m + j] = i * m + j } } u := &unionFindSet{} u.UnionSet = unionSet u.Count = count dires := []struct{x, y int}{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == '0' { continue } //判断当前节点周围是否有挨着的1 for _, d := range dires { x := i + d.x y := j + d.y if 0 <= x && x < n && 0 <= y && y < m && grid[x][y] == '1' { u.union(i * m + j, x * m + y) } } } } return u.Count } type unionFindSet struct { UnionSet []int Count int } func (ufs *unionFindSet) union(x, y int) { xRoot := ufs.unionFindRoot(x) yRoot := ufs.unionFindRoot(y) if xRoot != yRoot { ufs.UnionSet[xRoot] = yRoot ufs.Count-- } } func (ufs *unionFindSet) unionFindRoot(k int) int { //根结点的值等于它本身 if ufs.UnionSet[k] != k { ufs.UnionSet[k] = ufs.unionFindRoot(ufs.UnionSet[k]) } return ufs.UnionSet[k] }