一、题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

点击查看原题
难度级别： 中等

二、思路

1）DFS

使用visited记录进行深度搜索过的空格，不会重复计数岛屿（这里可以使用原本的数组空间进行优化，这里本着不想更改源数据的想法进行编码），每进行一次dfs，岛屿数量自增一

2）并查集

并查集可以将连在一起的格子都指向一个根节点，将二维数组一维化，就可以使用并查集进行解题

三、代码

1）DFS

  1. class Solution {
  2.     private boolean[][] visited;
  3.     private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  4.     public int numIslands(char[][] grid) {
  5.         visited = new boolean[grid.length][grid[0].length];
  6.         int ans = 0;
  8.         for (int i = 0; i < grid.length; i++) {
  9.             for (int j = 0; j < grid[0].length; j++) {
  10.                 if (visited[i][j] == false && grid[i][j] == '1') {
  11.                     dfs(grid, i, j);
  12.                     ans++;
  13.                 }
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18.     public void dfs(char[][] grid, int row, int col) {
  19.         if (grid[row][col] == '0') {
  20.             return ;
  21.         }
  22.         visited[row][col] = true;
  23.         for (int[] dir : dirs) {
  24.             int newRow = row + dir[0];
  25.             int newCol = col + dir[1];
  26.             if (newRow >= 0 && newRow < grid.length 
  27.                     && newCol >= 0 && newCol < grid[0].length 
  28.                     && visited[newRow][newCol] == false) {
  29.                 dfs(grid, newRow, newCol);
  30.             }
  31.         }
  32.     }
  33. }

时间复杂度为O(m*n)，空间复杂度为O(m*n)

2）并查集

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.         int oneCnt = 0;
  4.         UnionFind uf = new UnionFind(grid.length * grid[0].length);
  5.         int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  7.         for (int i = 0; i < grid.length; i++) {
  8.             for (int j = 0; j < grid[0].length; j++) {
  9.                 if (grid[i][j] == '1') {
  10.                     oneCnt++;
  11.                     for (int[] dir : dirs) {
  12.                         int newI = i + dir[0];
  13.                         int newJ = j + dir[1];
  14.                         if (newI >= 0 && newI < grid.length
  15.                                 && newJ >= 0 && newJ < grid[0].length
  16.                                 && grid[newI][newJ] == '1') {
  17.                             uf.union(i*grid[0].length + j, newI *grid[0].length + newJ);
  18.                         }
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.         return oneCnt - uf.getMeregeCnt();
  24.     }
  25. }
  26. class UnionFind {
  27.     private int[] ranks;
  28.     private int[] parents;
  29.     private int meregeCnt = 0;
  30.     public UnionFind(int n) {
  31.         ranks = new int[n+1];
  32.         parents = new int[n+1];
  33.         for (int i = 1; i < n; i++) {
  34.             parents[i] = i;
  35.         }
  36.     }
  37.     public int findParent(int x) {
  38.         if (parents[x] != x) {
  39.             parents[x] = findParent(parents[x]);
  40.         }
  41.         return parents[x];
  42.     }
  43.     public void union(int x, int y) {
  44.         int xP = findParent(x);
  45.         int yP = findParent(y);
  46.         if (xP == yP) {
  47.             return ;
  48.         }
  49.         if (ranks[xP] > ranks[yP]) {
  50.             parents[yP] = xP;
  51.         } else if (ranks[xP] < ranks[yP]) {
  52.             parents[xP] = yP;
  53.         } else {
  54.             parents[yP] = xP;
  55.             ranks[xP]++;
  56.         }
  57.         meregeCnt++;
  58.     }
  59.     public int getMeregeCnt() {
  60.         return meregeCnt;
  61.     }
  62. }

a是四次union的时间，时间复杂度为O(m*n*a)，空间复杂度为O(m*n)