这里是问题描述。前两个建议的解决方案涉及DFS和BFS。这个问题涉及到前两种方法：DFS和BFS。
我已经在这里包含了问题陈述以便更容易阅读。
Given a 2d grid map of '1's (land) and '0's (water), count the number of
islands. An island is surrounded by water and is formed by connecting adjacent
lands horizontally or vertically. You may assume all four edges of the grid are
all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
我不清楚为什么DFS和BFS的时间复杂度都是O(rows * columns)。我知道当网格只包含0时，这种情况就会发生 - 我们只需检查每个单元格即可。但是，DFS方法是否会增加搜索时间呢？即使我们通过在dfs方法中将它们更改为0来标记访问过的单元格，由于两个外部循环，我们仍然会重新访问所有单元格。如果在具有大行数和列数的大网格的情况下，DFS的时间复杂度可以达到O(n)，那么时间复杂度不应该是O(rows * columns * max[rows, cols])吗？此外，BFS方法的情况也是一样的，其时间复杂度为O(rows * cols * possibleMaxSizeOfQueue)，其中possibleMaxSizeOfQueue可能再次是max[rows,cols]。
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
DFS的空间复杂度为O(rows*cols)，为什么不能/不常考虑递归分支返回时调用栈空间被释放呢？
BFS的空间复杂度为O(min(rows, cols))。就我所见，在网格只有1的情况下，队列可能会装满所有元素，因此BFS的空间复杂度为O(rows*cols)。
DFS解决方案
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
时间复杂度：O(M×N)，其中M是行数，N是列数。
空间复杂度：最坏情况下为O(M×N)，即当网格图中全部为陆地时，DFS深度为M×N。
BFS解法
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
时间复杂度：O（M×N），其中M是行数，N是列数。
空间复杂度：O（min（M，N）），因为在最坏情况下，即网格被陆地填满时，队列的大小可能增长到min（M，N）。
O(min(rows, cols))的结论？我认为它应该是O(rows * cols)，因为你需要为每个网格单元存储数据。如果这个结论在链接的解决方案中，我没有账号就无法查看。 - k_ssb