岛屿数量

Number of Islands

专题: Algorithmic Programming / 算法编程
难度: L3
来源: Citadel

个人笔记

题目详情

问题：岛屿数量

考察：图、数组

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/number-of-islands/

英文原题

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

解析

思路：遍历网格，遇到未访问的陆地就计数并用 DFS/BFS 把与它四联通的陆地全部标记访问。

复杂度：时间 O(mn)，空间 O(mn) 最坏递归/队列。

英文解析

Approach: Scan the grid. Whenever an unvisited land cell is found, start DFS/BFS to mark its whole connected component, then increment the island count.

Complexity: Time $O(mn)$ , space $O(mn)$ worst case.