200. 岛屿数量

本题来自 LeetCode：200. 岛屿数量^[1]

题目描述

给定一个由  ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例  2:

输入:
11000
11000
00100
00011

输出: 3

深度搜索

题目分析

题目要求岛屿的数量，一个岛屿是被水 0包围的一整片陆地 1，那么需要将这种被水 0隔离的整片陆地 1的区域计算出来。
可以采用深度遍历，找到其中一块陆地 1，然后遍历其 上下左右四个方向，将每个被访问过的陆地置为已访问，这样就能标识这个岛屿的区域了。

题目解答

class Solution {
    private static final char VISITED = '#';
    private static final char LAND = '1';
    private static final char WATER = '0';

    public int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length;
        // 考虑下这个case
        if(m == 0) {
            return 0;
        }
        int n = grid[0].length;
        // 遍历grid数组的每一个值
        for(int i = 0; i  m; i ++) {
            for(int j = 0; j  n; j ++) {
                // 若当前不是岛屿（可能是已访问的岛屿，或者是水），则跳过
                if(grid[i][j] != LAND) {
                    continue;
                }
                // 将与当前岛屿相邻的岛屿全部置为已访问
                visitLand(grid, m, n, i, j);
                count ++;
            }
        }
        return count;
    }
    public void visitLand(char[][] grid, int m, int n, int i, int j) {
        // 越界，直接返回
        if(i  0 || i == m || j  0 || j == n) {
            return;
        }
        // 已访问，或者是水，直接返回
        if(grid[i][j] != LAND) {
            return;
        }
        grid[i][j] = VISITED;
        // left
        visitLand(grid, m, n, i - 1, j);
        // right
        visitLand(grid, m, n, i + 1, j);
        // up
        visitLand(grid, m, n, i, j - 1);
        // down
        visitLand(grid, m, n, i, j + 1);
    }
}

复杂度分析：
时间复杂度： O(m * n)
空间复杂度： O(m * n)

广度搜索

题目分析

也可以采用广度搜索来解答。注意点是对每一个加入到队列的元素，要先标记为已访问，否则会存在很多重复的。

题目解答

class Solution {
    private static final char VISITED = '#';
    private static final char LAND = '1';
    private static final char WATER = '0';

    class Position {
        int row;
        int column;

        Position(int row, int column) {
            this.row = row;
            this.column = column;
        }
    }

    public int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length;
        // 考虑下这个case
        if(m == 0) {
            return 0;
        }
        int n = grid[0].length;
        // 遍历grid数组的每一个值
        for(int i = 0; i  m; i ++) {
            for(int j = 0; j  n; j ++) {
                // 若当前不是岛屿（可能是已访问的岛屿，或者是水），则跳过
                if(grid[i][j] != LAND) {
                    continue;
                }
                count ++;
                ListPosition queue = new LinkedList();
                // 标记为已访问
                grid[i][j] = VISITED;
                // 广度搜索
                queue.add(new Position(i, j));
                while(!queue.isEmpty()) {
                    Position position = queue.remove(0);
                    int row = position.row;
                    int column = position.column;
                    // left
                    if(row  0 && grid[row -1][column] == LAND) {
                        queue.add(new Position(row - 1, column));
                        // 先标记为访问
                        grid[row - 1][column] = VISITED;
                    }
                    // right
                    if(row  m - 1 && grid[row + 1][column] == LAND) {
                        queue.add(new Position(row + 1, column));
                        grid[row + 1][column] = VISITED;
                    }
                    //up
                    if(column  0 && grid[row][column - 1] == LAND) {
                        queue.add(new Position(row, column - 1));
                        grid[row][column - 1] = VISITED;
                    }
                    // down
                    if(column  n - 1 && grid[row][column + 1] == LAND) {
                        queue.add(new Position(row, column + 1));
                        grid[row][column + 1] = VISITED;
                    }
                }
            }
        }
        return count;
    }
}

复杂度分析：
时间复杂度： O(m * n)
空间复杂度： O(min(m, n))，在最坏的情况下（全部为陆地），队列的大小可以达到 min(m，n)。

也可以采用并查集来解答，后面还有专题来解答并查集相关的题。

参考资料

200. 岛屿数量: https://leetcode-cn.com/problems/number-of-islands

原文始发于微信公众号（xiaogan的技术博客）：