LeetCode 200. 岛屿数量
题目描述
题目：
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿四面被水包围，由水平或垂直方向相邻的陆地连接而成，网格四条边均视为水域。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300-
grid[i][j]的值为'0'或'1'
思路分析
解法一：DFS（网格遍历）（推荐）
核心思路：
- 遍历网格，遇到
'1'说明发现新岛屿，计数加一。- 用 DFS 将该岛屿的所有相连陆地标记为
'0'，避免重复统计。- 相邻方向只需上下左右四个方向。
复杂度分析：
- 时间复杂度：O(mn)，其中 m、n 分别表示网格行列数。
- 空间复杂度：O(mn)，其中 m、n 表示递归栈最坏深度。
// DFS 沉岛标记
class Solution {
public int numIslands(char[][] grid) {
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) {
return;
}
if (grid[i][j] != '1') {
return;
}
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
// DFS 沉岛标记
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
count := 0
var dfs func(int, int)
dfs = func(i, j int) {
if i < 0 || i >= m || j < 0 || j >= n {
return
}
if grid[i][j] != '1' {
return
}
grid[i][j] = '0'
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
count++
dfs(i, j)
}
}
}
return count
}
解法二：并查集
核心思路：
- 将每个陆地格子映射到并查集节点。
- 初始岛屿数量为陆地数量，合并相邻陆地时数量减一。
- 最终并查集中的集合数即岛屿数量。
复杂度分析：
- 时间复杂度：O(mn α(mn))，其中 m、n 表示网格行列数，α 为反阿克曼函数。
- 空间复杂度：O(mn)，其中 m、n 表示并查集数组大小。
{% raw %}
// 并查集统计连通分量
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
UnionFind uf = new UnionFind(grid);
int[][] dirs = {{1, 0}, {0, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '1') {
continue;
}
for (int[] d : dirs) {
int ni = i + d[0];
int nj = j + d[1];
if (ni < m && nj < n && grid[ni][nj] == '1') {
uf.union(i * n + j, ni * n + nj);
}
}
}
}
return uf.getCount();
}
private static class UnionFind {
private final int[] parent;
private final int[] rank;
private int count;
UnionFind(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int idx = i * n + j;
if (grid[i][j] == '1') {
parent[idx] = idx;
count++;
} else {
parent[idx] = -1;
}
}
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int x, int y) {
if (parent[x] == -1 || parent[y] == -1) {
return;
}
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
}
int getCount() {
return count;
}
}
}
{% endraw %}
{% raw %}
// 并查集统计连通分量
type UnionFind struct {
parent []int
rank []int
count int
}
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
uf := newUnionFind(grid)
dirs := [][2]int{{1, 0}, {0, 1}}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != '1' {
continue
}
for _, d := range dirs {
ni := i + d[0]
nj := j + d[1]
if ni < m && nj < n && grid[ni][nj] == '1' {
uf.union(i*n+j, ni*n+nj)
}
}
}
}
return uf.count
}
func newUnionFind(grid [][]byte) *UnionFind {
m, n := len(grid), len(grid[0])
parent := make([]int, m*n)
rank := make([]int, m*n)
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
idx := i*n + j
if grid[i][j] == '1' {
parent[idx] = idx
count++
} else {
parent[idx] = -1
}
}
}
return &UnionFind{parent: parent, rank: rank, count: count}
}
func (uf *UnionFind) find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) union(x, y int) {
if uf.parent[x] == -1 || uf.parent[y] == -1 {
return
}
rootX := uf.find(x)
rootY := uf.find(y)
if rootX == rootY {
return
}
if uf.rank[rootX] < uf.rank[rootY] {
uf.parent[rootX] = rootY
} else if uf.rank[rootX] > uf.rank[rootY] {
uf.parent[rootY] = rootX
} else {
uf.parent[rootY] = rootX
uf.rank[rootX]++
}
uf.count--
}
{% endraw %}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 130. 被围绕的区域 | 中等 | DFS、并查集 |
| 419. 棋盘上的战舰 | 中等 | 网格遍历 |
| 695. 岛屿的最大面积 | 中等 | DFS、BFS |
| 1905. 统计子岛屿 | 中等 | DFS |
| 1992. 找到所有的农场组 | 中等 | DFS |
| 2316. 统计无向图中无法互相到达点对数 | 中等 | 并查集、DFS |
| 2658. 网格图中鱼的最大数目 | 中等 | DFS |
| 3619. 总价值可以被 K 整除的岛屿数目 | 中等 | DFS |
| 463. 岛屿的周长 | 简单 | 网格遍历 |
| 547. 省份数量 | 中等 | 并查集、DFS |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！