leetcode hot 100-力扣200. 岛屿数量

 下面这题我刚开始一直以为是求图的连通分量的个数,弄了好久发现总是有问题,后来才发现不是连通分量的题型,连通分量求的是顶点的被分成多少块,下面这种题目是一个矩阵被分成多少块,两者不一样

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/

上一篇:css-:after伪样式


下一篇:LeetCode Hot 100 No.53 最大子序和