题解 | 岛屿数量

1、解题思路

1. 深度优先搜索 (DFS)：遍历矩阵的每一个元素，当遇到一个未被访问的1时，进行DFS或BFS，标记所有相邻的1为已访问。每次发现一个新的未被访问的1，岛屿计数加一。时间复杂度：O(m*n)，空间复杂度：O(m*n)（最坏情况下递归栈的深度）。
2. 广度优先搜索 (BFS)：使用队列来实现BFS，同样遍历矩阵，遇到未被访问的1时进行BFS。时间复杂度：O(m*n)，空间复杂度：O(m*n)（队列的存储空间）。
3. 并查集 (Union-Find)：可以使用并查集来合并相邻的1，最终统计连通分量的数量。时间复杂度：O(m*n)，空间复杂度：O(m*n)。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here
        if (grid.empty()) {
            return 0;
        }

        int m = grid.size();
        int n = grid[0].size();
        int count = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() ||
                grid[i][j] != '1') {
            return ;
        }

        grid[i][j] = '0';   // Mark as visited
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0'; // Mark as visited
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)
        return count

    def dfs(self, grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '0'  # Mark as visited
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)

3、复杂度分析

1. 标记访问：在DFS或BFS过程中，将访问过的1标记为0或其他字符，避免重复访问。
2. 边界检查：在递归或队列处理时，需要检查边界条件，避免数组越界。
3. 效率：时间复杂度：O(m*n)，因为每个元素最多被访问一次。空间复杂度：O(m*n)，最坏情况下递归栈或队列的深度。
4. 适用性：DFS和BFS都是解决岛屿问题的经典方法，适用于大规模数据。并查集适用于需要动态合并和查询连通性的场景。