Question

200. 岛屿数量

English Version

题目描述

给你一个由 '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.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

解法

方法一：Flood fill 算法

Flood fill 算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。

最简单的实现方法是采用 DFS 的递归方法，也可以采用 BFS 的迭代来实现。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为网格的行数和列数。

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    def dfs(i, j):
      grid[i][j] = '0'
      for a, b in pairwise(dirs):
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
          dfs(x, y)

    ans = 0
    dirs = (-1, 0, 1, 0, -1)
    m, n = len(grid), len(grid[0])
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '1':
          dfs(i, j)
          ans += 1
    return ans

class Solution {
  private char[][] grid;
  private int m;
  private int n;

  public int numIslands(char[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          dfs(i, j);
          ++ans;
        }
      }
    }
    return ans;
  }

  private void dfs(int i, int j) {
    grid[i][j] = '0';
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k];
      int y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
        dfs(x, y);
      }
    }
  }
}

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int)> dfs = [&](int i, int j) {
      grid[i][j] = '0';
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
          dfs(x, y);
        }
      }
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          dfs(i, j);
          ++ans;
        }
      }
    }
    return ans;
  }
};

func numIslands(grid [][]byte) int {
  m, n := len(grid), len(grid[0])
  var dfs func(i, j int)
  dfs = func(i, j int) {
    grid[i][j] = '0'
    dirs := []int{-1, 0, 1, 0, -1}
    for k := 0; k < 4; k++ {
      x, y := i+dirs[k], j+dirs[k+1]
      if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
        dfs(x, y)
      }
    }
  }
  ans := 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == '1' {
        dfs(i, j)
        ans++
      }
    }
  }
  return ans
}

function numIslands(grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  let ans = 0;
  function dfs(i, j) {
    grid[i][j] = '0';
    const dirs = [-1, 0, 1, 0, -1];
    for (let k = 0; k < 4; ++k) {
      const x = i + dirs[k];
      const y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
        dfs(x, y);
      }
    }
  }
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] == '1') {
        dfs(i, j);
        ++ans;
      }
    }
  }
  return ans;
}

const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];

impl Solution {
  pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
    fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
      grid[i][j] = '0';
      for k in 0..4 {
        let x = (i as i32) + DIRS[k];
        let y = (j as i32) + DIRS[k + 1];
        if
          x >= 0 &&
          (x as usize) < grid.len() &&
          y >= 0 &&
          (y as usize) < grid[0].len() &&
          grid[x as usize][y as usize] == '1'
        {
          dfs(grid, x as usize, y as usize);
        }
      }
    }

    let mut grid = grid;
    let mut ans = 0;
    for i in 0..grid.len() {
      for j in 0..grid[0].len() {
        if grid[i][j] == '1' {
          dfs(&mut grid, i, j);
          ans += 1;
        }
      }
    }
    ans
  }
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
  public int NumIslands(char[][] grid)
  {
    var queue = new Queue<Tuple<int, int>>();
    var lenI = grid.Length;
    var lenJ = lenI == 0 ? 0 : grid[0].Length;
    var paths = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    var result = 0;
    for (var i = 0; i < lenI; ++i)
    {
      for (var j = 0; j < lenJ; ++j)
      {
        if (grid[i][j] == '1')
        {
          ++result;
          grid[i][j] = '0';
          queue.Enqueue(Tuple.Create(i, j));
          while (queue.Any())
          {
            var position = queue.Dequeue();
            for (var k = 0; k < 4; ++k)
            {
              var next = Tuple.Create(position.Item1 + paths[k, 0], position.Item2 + paths[k, 1]);
              if (next.Item1 >= 0 && next.Item1 < lenI && next.Item2 >= 0 && next.Item2 < lenJ && grid[next.Item1][next.Item2] == '1')
              {
                grid[next.Item1][next.Item2] = '0';
                queue.Enqueue(next);
              }
            }
          }
        }
      }
    }
    return result;
  }
}

方法二：并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。 它支持两种操作：

1. 查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度 $O(\alpha(n))$
2. 合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度 $O(\alpha(n))$

其中 $\alpha$ 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

以下是并查集的常用模板，需要熟练掌握。其中：

• n 表示节点数
• p 存储每个点的父节点，初始时每个点的父节点都是自己
• size 只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
• find(x) 函数用于查找 $x$ 所在集合的祖宗节点
• union(a, b) 函数用于合并 $a$ 和 $b$ 所在的集合

p = list(range(n))
size = [1] * n


def find(x):
  if p[x] != x:
    # 路径压缩
    p[x] = find(p[x])
  return p[x]


def union(a, b):
  pa, pb = find(a), find(b)
  if pa == pb:
    return
  p[pa] = pb
  size[pb] += size[pa]

时间复杂度 $O(m\times n\times \alpha(m\times n))$。其中 $m$ 和 $n$ 分别为网格的行数和列数。

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    def bfs(i, j):
      grid[i][j] = '0'
      q = deque([(i, j)])
      while q:
        i, j = q.popleft()
        for a, b in pairwise(dirs):
          x, y = i + a, j + b
          if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
            q.append((x, y))
            grid[x][y] = 0

    ans = 0
    dirs = (-1, 0, 1, 0, -1)
    m, n = len(grid), len(grid[0])
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '1':
          bfs(i, j)
          ans += 1
    return ans

class Solution {
  private char[][] grid;
  private int m;
  private int n;

  public int numIslands(char[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          bfs(i, j);
          ++ans;
        }
      }
    }
    return ans;
  }

  private void bfs(int i, int j) {
    grid[i][j] = '0';
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {i, j});
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int[] p = q.poll();
      for (int k = 0; k < 4; ++k) {
        int x = p[0] + dirs[k];
        int y = p[1] + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
          q.offer(new int[] {x, y});
          grid[x][y] = '0';
        }
      }
    }
  }
}

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int)> bfs = [&](int i, int j) {
      grid[i][j] = '0';
      queue<pair<int, int>> q;
      q.push({i, j});
      vector<int> dirs = {-1, 0, 1, 0, -1};
      while (!q.empty()) {
        auto [a, b] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          int x = a + dirs[k];
          int y = b + dirs[k + 1];
          if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
            q.push({x, y});
            grid[x][y] = '0';
          }
        }
      }
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          bfs(i, j);
          ++ans;
        }
      }
    }
    return ans;
  }
};

func numIslands(grid [][]byte) int {
  m, n := len(grid), len(grid[0])
  bfs := func(i, j int) {
    grid[i][j] = '0'
    q := [][]int{[]int{i, j}}
    dirs := []int{-1, 0, 1, 0, -1}
    for len(q) > 0 {
      p := q[0]
      q = q[1:]
      for k := 0; k < 4; k++ {
        x, y := p[0]+dirs[k], p[1]+dirs[k+1]
        if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
          q = append(q, []int{x, y})
          grid[x][y] = '0'
        }
      }
    }
  }
  ans := 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == '1' {
        bfs(i, j)
        ans++
      }
    }
  }
  return ans
}

function numIslands(grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  let ans = 0;
  function bfs(i, j) {
    grid[i][j] = '0';
    let q = [[i, j]];
    const dirs = [-1, 0, 1, 0, -1];
    while (q.length) {
      [i, j] = q.shift();
      for (let k = 0; k < 4; ++k) {
        const x = i + dirs[k];
        const y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
          q.push([x, y]);
          grid[x][y] = '0';
        }
      }
    }
  }
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] == '1') {
        bfs(i, j);
        ++ans;
      }
    }
  }
  return ans;
}

use std::collections::VecDeque;

const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];

impl Solution {
  pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
    fn bfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
      grid[i][j] = '0';
      let mut queue = VecDeque::from([(i, j)]);
      while !queue.is_empty() {
        let (i, j) = queue.pop_front().unwrap();
        for k in 0..4 {
          let x = (i as i32) + DIRS[k];
          let y = (j as i32) + DIRS[k + 1];
          if
            x >= 0 &&
            (x as usize) < grid.len() &&
            y >= 0 &&
            (y as usize) < grid[0].len() &&
            grid[x as usize][y as usize] == '1'
          {
            grid[x as usize][y as usize] = '0';
            queue.push_back((x as usize, y as usize));
          }
        }
      }
    }

    let mut grid = grid;
    let mut ans = 0;
    for i in 0..grid.len() {
      for j in 0..grid[0].len() {
        if grid[i][j] == '1' {
          bfs(&mut grid, i, j);
          ans += 1;
        }
      }
    }
    ans
  }
}

方法三

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    dirs = (0, 1, 0)
    m, n = len(grid), len(grid[0])
    p = list(range(m * n))
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '1':
          for a, b in pairwise(dirs):
            x, y = i + a, j + b
            if x < m and y < n and grid[x][y] == '1':
              p[find(i * n + j)] = find(x * n + y)
    return sum(
      grid[i][j] == '1' and i * n + j == find(i * n + j)
      for i in range(m)
      for j in range(n)
    )

class Solution {
  private int[] p;

  public int numIslands(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    p = new int[m * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    int[] dirs = {1, 0, 1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          for (int k = 0; k < 2; ++k) {
            int x = i + dirs[k];
            int y = j + dirs[k + 1];
            if (x < m && y < n && grid[x][y] == '1') {
              p[find(x * n + y)] = find(i * n + j);
            }
          }
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1' && i * n + j == find(i * n + j)) {
          ++ans;
        }
      }
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<int> p(m * n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    int dirs[3] = {1, 0, 1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          for (int k = 0; k < 2; ++k) {
            int x = i + dirs[k];
            int y = j + dirs[k + 1];
            if (x < m && y < n && grid[x][y] == '1') {
              p[find(x * n + y)] = find(i * n + j);
            }
          }
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans += grid[i][j] == '1' && i * n + j == find(i * n + j);
      }
    }
    return ans;
  }
};

func numIslands(grid [][]byte) int {
  m, n := len(grid), len(grid[0])
  p := make([]int, m*n)
  for i := range p {
    p[i] = i
  }
  var find func(x int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  dirs := []int{1, 0, 1}
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == '1' {
        for k := 0; k < 2; k++ {
          x, y := i+dirs[k], j+dirs[k+1]
          if x < m && y < n && grid[x][y] == '1' {
            p[find(x*n+y)] = find(i*n + j)
          }
        }
      }
    }
  }
  ans := 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == '1' && i*n+j == find(i*n+j) {
        ans++
      }
    }
  }
  return ans
}

function numIslands(grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  let p = [];
  for (let i = 0; i < m * n; ++i) {
    p.push(i);
  }
  function find(x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
  const dirs = [1, 0, 1];
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] == '1') {
        for (let k = 0; k < 2; ++k) {
          const x = i + dirs[k];
          const y = j + dirs[k + 1];
          if (x < m && y < n && grid[x][y] == '1') {
            p[find(i * n + j)] = find(x * n + y);
          }
        }
      }
    }
  }
  let ans = 0;
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] == '1' && i * n + j == find(i * n + j)) {
        ++ans;
      }
    }
  }
  return ans;
}

const DIRS: [usize; 3] = [1, 0, 1];

impl Solution {
  pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut p: Vec<i32> = (0..(m * n) as i32).collect();

    fn find(p: &mut Vec<i32>, x: usize) -> i32 {
      if p[x] != (x as i32) {
        p[x] = find(p, p[x] as usize);
      }
      p[x]
    }

    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == '1' {
          for k in 0..2 {
            let x = i + DIRS[k];
            let y = j + DIRS[k + 1];
            if x < m && y < n && grid[x][y] == '1' {
              let f1 = find(&mut p, x * n + y);
              let f2 = find(&mut p, i * n + j);
              p[f1 as usize] = f2;
            }
          }
        }
      }
    }

    let mut ans = 0;
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == '1' && p[i * n + j] == ((i * n + j) as i32) {
          ans += 1;
        }
      }
    }
    ans
  }
}