下面这题我刚开始一直以为是求图的连通分量的个数，弄了好久发现总是有问题，后来才发现不是连通分量的题型，连通分量求的是顶点的被分成多少块，下面这种题目是一个矩阵被分成多少块，两者不一样
200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入: 11110 11010 11000 00000 输出: 1
示例 2:
输入: 11000 11000 00100 00011 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
思路一：dfs
遍历矩阵,如果当前元素没有被遍历过且值不为“0”，递归遍历它,把所有直接与他相连的位置都标记为已访问，岛屿数加一。最终岛屿的数量就是我们在主函数中调用 dfs() 函数的次数。
对于dfs函数：从某个元素开始dfs递归遍历所有与它相连的元素，访问过的元素标记vis[]为true，访问四个方向
1 class Solution {
2
3 public boolean[][] vis;
4 public int rows;
5 public int cols;
6 public char[][] grid;
7
8 public int numIslands(char[][] grid) {
9 if(grid == null || grid.length == 0){
10 return 0;
11 }
12
13 rows = grid.length;
14 cols = grid[0].length;
15 this.grid = grid;
16
17 vis = new boolean[rows][cols];
18
19 // 遍历矩阵
20 int count = 0;
21 for(int i = 0; i < rows; i++){
22 for(int j = 0; j < cols; j++){
23 // 如果当前元素没有被遍历过且值不为“0”，递归遍历它
24 if(vis[i][j] == false && grid[i][j] != '0'){
25 dfs(i, j);
26 count++; // 岛屿数加一
27 }
28 }
29 }
30 return count;
31 }
32 public int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
33
34 // 从某个元素开始dfs递归遍历所有与它相连的元素
35 // 访问过的元素标记vis[]为true
36 public void dfs(int row, int col){
37 vis[row][col] = true; // 标记该位置为已访问
38
39 // 访问四个方向
40 for(int i = 0; i < 4; i++){
41 int newRow = row + dir[i][0];
42 int newCol = col + dir[i][1];
43 if(newRow < rows && newRow >= 0 && newCol < cols && newCol >= 0
44 && vis[newRow][newCol] == false && grid[newRow][newCol] != '0'){
45 dfs(newRow, newCol);
46 }
47 }
48 }
49 }
leetcode 运行时间为3ms, 空间为40.7MB
复杂度分析：
时间复杂度：numIslands()函数中的双重循环其实只有少部分会进入dfs进行递归，不进入递归的迭代相比于进入迭代的情况花费的时间是非常短的，所以主要看进入递归的那些位置，而每次调用 dfs() 函数都会把所有与当前位置相连的 '1' 都遍历一遍， 也就是把当前 ‘1' 所在的岛屿遍历一遍，每个岛屿和每个岛屿的元素都会被遍历且仅被遍历一遍，所以当把所有的岛屿到找出来，相当于把矩阵中所有的 '1' 都遍历了一遍，所以算法的时间复杂度其实和矩阵中的 '1' 的个数是正相关的，所以算法的最坏时间复杂度为O(n*m), 也就是当矩阵都是 '1'的时候。
空间复杂度：使用了一个额外的vis[][]数组，花费的空间大小为O(M*N), 另一部分递归栈的开销当所有位置都是1的时候，递归的深度最大为M*N, 所以空间复杂度为O(M*N)
其实可以不使用一个vis[][]数组，直接把访问过的元素标记为 '0'，即可，这样可以省去一部分空间
1 class Solution {
2
3 int rows, cols;
4 // dfs遍历一个与(i,j)都相连的4个单元
5 void dfs(char[][]grid, int x, int y){
6 // 把grid[x][y]标记为0，即使设置为已访问
7 grid[x][y] = '0';
8
9 // 遍历四个方向的单元
10 if(x - 1 >= 0 && grid[x-1][y] == '1'){
11 dfs(grid, x-1, y);
12 }
13 if(x + 1 < rows && grid[x+1][y] == '1'){
14 dfs(grid, x+1, y);
15 }
16
17 if(y - 1 >= 0 && grid[x][y-1] == '1'){
18 dfs(grid, x, y-1);
19 }
20 if(y + 1 < cols && grid[x][y+1] == '1'){
21 dfs(grid, x, y+1);
22 }
23 }
24
25
26 public int numIslands(char[][] grid) {
27 if(grid == null || (grid != null && grid.length == 0))
28 return 0;
29
30 rows = grid.length;
31 cols = grid[0].length;
32
33 int cnt = 0;
34 // 遍历矩阵
35 for(int i = 0; i < rows; i++){
36 for(int j = 0; j < cols; j++){
37 if(grid[i][j] == '1'){ // 只有当前位置为1才能去访问它
38 cnt++;
39 dfs(grid, i, j);
40 }
41 }
42 }
43 return cnt;
44 }
45 }
力扣测试时间为1ms, 空间为42.4MB
复杂度分析：
时间复杂度：同思路一
空间复杂度：比思路一少一个vis[][]的O(N*M)的空间开销，但是因为递归栈的存在，所以空间复杂度仍然为O(N*M)
思路二：BFS
我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行广度优先搜索。在广度优先搜索的过程中，每次把位置加入队列后就把这个位置置为'0'
1 class Solution {
2
3 public int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
4
5 public int numIslands(char[][] grid) {
6 if(grid == null || grid.length == 0){
7 return 0;
8 }
9
10 int rows = grid.length;
11 int cols = grid[0].length;
12 this.grid = grid;
13
14 // 遍历矩阵
15 int count = 0;
16 for(int i = 0; i < rows; i++){
17 for(int j = 0; j < cols; j++){
18 // 如果当前元素没有被遍历过且值不为'0'，bfs遍历它
19 if(grid[i][j] != '0'){
20 // bfs遍历
21
22 grid[i][j] = '0'; // 注意
23 // 把当前元素位置放入队列
24 Pair<Integer, Integer> pair = new Pair<>(i, j);
25 Queue<Pair> queue = new LinkedList<>();
26 queue.offer(pair);
27 while(!queue.isEmpty()){
28 // 从队列中取出一个位置
29 pair = queue.poll();
30 int row = pair.getKey();
31 int col = pair.getValue();
32 // 遍历四个方向
33 for(int k = 0; k < 4; k++){
34 int newRow = row + dir[k][0];
35 int newCol = col + dir[k][1];
36 // 对每个方向的元素如果值为'1'且位置不越界则放入队列
37 if(newRow < rows && newRow >= 0 && newCol < cols && newCol >= 0
38 && grid[newRow][newCol] != '0'){
39 grid[newRow][newCol] = '0'; // 注意这行代码
40 queue.offer(new Pair<Integer, Integer>(newRow, newCol));
41 }
42 }
43 }
44 count++; // 岛屿数加一
45 }
46 }
47 }
48 return count;
49 }
50 }
leetcode 执行用时：7 ms > 9.68%, 内存消耗：41.1 MB > 90.84%
复杂度分析：
时间复杂度和思路一一样
空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 4 * min(M, N)。
注意：
在上面代码中标红的代码，不能改成下面这种方式：否则会超时，因为在每次出队的时候才被标记为已访问，则有些位置可能会重复入队，造成重复计算。所以必须在元素入队时进行标记。
1 // 把当前元素位置放入队列
2 ...
3 while(!queue.isEmpty()){
4 // 从队列中取出一个位置
5 pair = queue.poll();
6 int row = pair.getKey();
7 int col = pair.getValue();
8 grid[row][col] = '0';
9 // 遍历四个方向
10 ...
11 }
思路三：并查集
将位置为(i,j)的坐标映射为parent数组的i * cols + j下标的元素，这样每个位置都能一一映射一个parent[]元素，从而可以改变其父节点
1 // 并查集实现
2 class Solution {
3 class UnionFind{
4 int rows; // 矩阵的行数
5 int cols; // 矩阵的列数
6 int[] parent; // 并查集数组
7 int[] rank; // 存储每个数字所在树的高度，有助于降低树的高度
8 int count = 0; // 记录岛屿数量
9
10 // 初始化parent[][]数组为下标本身，count值为1的个数
11 public UnionFind(char[][] grid){
12 rows = grid.length;
13 cols = grid[0].length;
14 parent = new int[rows * cols];
15 rank = new int[rows * cols];
16 for(int i = 0; i < rows; i++){
17 for(int j = 0; j < cols; j++){
18 if(grid[i][j] == '1'){
19 count++;
20 }
21 parent[cols * i + j] = cols * i + j;
22 rank[cols * i + j] = 0;
23 }
24 }
25 }
26
27 // 查找父节点
28 int findFather(int i){
29 if(parent[i] != i){
30 parent[i] = parent[parent[i]]; // 路径压缩
31 }
32 return parent[i];
33 }
34
35 // 合并两个点
36 public void union(int x, int y){
37 // 查找两个数字的父节点
38 int xfather = findFather(x);
39 int yfather = findFather(y);
40
41 // 如果不是同一个则合并，合并的时候矮的树挂到高的树上
42 if(xfather != yfather){
43 if(rank[xfather] > rank[yfather]){
44 parent[yfather] = xfather;
45 }else if(rank[xfather] < rank[yfather]){
46 parent[xfather] = yfather;
47 }else{
48 parent[xfather] = yfather;
49 rank[yfather]++; // 树的高度加一
50 }
51 count--; // 每合并两个结点，count就减一
52 }
53
54 }
55
56 int getCount(){
57 return count;
58 }
59 }
60
61
62 public int numIslands(char[][] grid) {
63 if(grid == null || (grid != null && grid.length == 0))
64 return 0;
65
66 int rows = grid.length;
67 int cols = grid[0].length;
68
69 UnionFind uf = new UnionFind(grid);
70 for(int i = 0; i < rows; i++){
71 for(int j = 0; j < cols; j++){ // 如果为1，则连接所有为1的四周结点
72 if(grid[i][j] == '1'){
73 grid[i][j] = '0';
74 if(i - 1 >= 0 && grid[i - 1][j] == '1')
75 uf.union(i * cols + j, (i - 1) * cols + j);
76 if(i + 1 < rows && grid[i + 1][j] == '1')
77 uf.union(i * cols + j, (i + 1) * cols + j);
78 if(j - 1 >= 0 && grid[i][j - 1] == '1')
79 uf.union(i * cols + j, i * cols + j - 1);
80 if(j + 1 < cols && grid[i][j + 1] == '1')
81 uf.union(i * cols + j, i * cols + j + 1);
82 }
83 }
84 }
85
86 return uf.getCount();
87 }
88 }
力扣测试时间为7ms, 空间为42.5MB
复杂度分析：
时间复杂度：取决于矩阵式中'1'的个数，所以时间复杂度为O(N*M)
空间复杂度：两个矩阵rank[]和parent[]，数组长度为N*M, 所以空间复杂度为O(N*M);
思路参考：
https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/