代码天涯路

200. 岛屿数量(Number of Islands)M

英文题目

  • Given an m x n 2d grid 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'.

中文题目

  • 给你一个由 '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'

DFS

  • 设目前指针指向一个岛屿中的某一点(i, j)，寻找包括此点的岛屿边界

  • 从(i, j)向上下左右的点进行深度搜索

  • 终止条件

    • 1.(i,j)越过矩阵边界
    • 2.grid[i][j] == 0，代表此分支已越过岛屿边界

  • 搜索岛屿的同时，执行grid[i][j] = '0'，把岛屿所有节点删除，以免之后重复搜索

  • 时间复杂度O(MN)，其中 M 和 N 分别为行数和列数。

  • 空间复杂度O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN

    # python3: 时间 108 ms, 击败 74.50%; 内存 26.6 MB, 击败 39.21%
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        res = 0
        row, col = len(grid), len(grid[0])

        for r in range(row):
            for c in range(col):
                if grid[r][c] == '1':
                    res += 1
                    self.dfs(grid, r, c)
        return res
    
    def dfs(self, grid: List[List[str]], r: int, c: int) -> None:
        grid[r][c] = '0'
        row, col = len(grid), len(grid[0])
        for x,y in [(r-1, c), (r, c-1), (r+1, c), (r, c+1)]:
            if 0 <= x < row and 0 <= y < col and grid[x][y] == '1':
                self.dfs(grid, x, y)

    // c++: 时间 24 ms, 击败 98.40%; 内存 12 MB, 击败 51.31%
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        int res = 0;
        int row = grid.size(), col = grid[0].size();
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '1') {
                    ++res;
                    dfs(grid, r, c);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int r, int c) {
        grid[r][c] = '0';
        int row = grid.size(), col = grid[0].size();
        int directions[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        for (int i = 0; i < 4; ++i) {
            int x = r + directions[i][0];
            int y = c + directions[i][1];
            if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }
};

    // java: 时间 3 ms, 击败 58.83%; 内存 48.7 MB, 击败 41.14%
class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int res = 0;
        int row = grid.length, col = grid[0].length;
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '1') {
                    ++res;
                    dfs(grid, r, c);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int r, int c) {
        grid[r][c] = '0';
        int row = grid.length, col = grid[0].length;
        int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        for (int i = 0; i < 4; ++i) {
            int x = r + directions[i][0];
            int y = c + directions[i][1];
            if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 3.7 MB, 击败 35.68%
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    res := 0
    row, col := len(grid), len(grid[0])
    for r := 0; r < row; r++ {
        for c := 0; c < col; c++ {
            if grid[r][c] == '1' {
                res++
                dfs(grid, r, c)
            }
        }
    }
    return res
}

func dfs(grid [][]byte, r, c int) {
    grid[r][c] = '0'
    row, col := len(grid), len((grid)[0])
    directions := [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
    for i := 0; i < 4; i++ {
        x := r + directions[i][0]
        y := c + directions[i][1]
        if 0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1' {
            dfs(grid, x, y)
        }
    }
}

    // javascript: 时间 76 ms, 击败 75.2%; 内存 49.1 MB, 击败 14.34%
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid.length) {
        return 0;
    }
    let res = 0;
    let row = grid.length, col = grid[0].length;
    for (let r = 0; r < row; ++r) {
        for (let c = 0; c < col; ++c) {
            if (grid[r][c] == '1') {
                ++res;
                dfs(grid, r, c);
            }
        }
    }
    return res;
};

const dfs = function(grid, r, c) {
    grid[r][c] = '0';
    let row = grid.length, col = grid[0].length;
    for (let d of [[-1, 0], [0, -1], [1, 0], [0,1]]) {
        let x = r + d[0];
        let y = c + d[1];
        if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
            dfs(grid, x, y);
        }
    }
}

BFS

  • 使用队列，把头部节点(i, j)未越界且为1的上下左右节点加入队列

  • 时间复杂度O(MN)，其中 M 和 N 分别为行数和列数。

  • 空间复杂度O(min(M,N))，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 min(M,N)

    # python3: 时间 120 ms, 击败 48.66%; 内存 26.4 MB, 击败 66.27%
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        res = 0
        row, col = len(grid), len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '1':
                    self.bfs(grid, r, c)
                    res += 1
        return res

    # 放入队列的都是'0'，且四周尚未探测的元素
    def bfs(self, grid: List[List[str]], r: int, c: int) -> None:
        queue = deque([(r,c), ])
        grid[r][c] = '0'
        row, col = len(grid), len(grid[0])
        while queue:
            curX, curY = queue.popleft()
            for x, y in [(curX-1, curY), (curX, curY-1), (curX+1, curY), (curX, curY+1)]:
                if 0 <= x < row and 0 <= y < col and grid[x][y] == '1':
                    queue.append((x, y))
                    grid[x][y] = '0'

    // c++: 时间 32 ms, 击败 65.90%; 内存 17.31 MB, 击败 12.12%
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        int res = 0;
        int row = grid.size(), col = grid[0].size();
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '1') {
                    ++res;
                    bfs(grid, r, c);
                }
            }
        }
        return res;
    }

    // 放入队列中的都是'0'，但其四周都尚未探测的元素
    void bfs(vector<vector<char>>& grid, int r, int c) {
        queue<pair<int, int>> q;
        q.push(make_pair(r, c));
        grid[r][c] = '0';
        int row = grid.size(), col = grid[0].size();
        int directions[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while (!q.empty()) {
            int curX, curY;
            tie(curX, curY) = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int x = curX + directions[i][0];
                int y = curY + directions[i][1];
                if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                    q.push({x, y});
                    grid[x][y] = '0';
                }
            }
        }
    }
};

    // java: 时间 4 ms, 击败 33.27%; 内存 48.9 MB, 击败 38.97%
class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int res = 0;
        int row = grid.length, col = grid[0].length;
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '1') {
                    ++res;
                    bfs(grid, r, c);
                }
            }
        }
        return res;
    }

    private void bfs(char[][] grid, int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        grid[r][c] = '0';
        int row = grid.length, col = grid[0].length;
        int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];
            for (int i = 0; i < 4; i++) {
                int x = curX + directions[i][0];
                int y = curY + directions[i][1];
                if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                    q.add(new int[]{x, y});
                    grid[x][y] = '0';
                }
            }
        }
    }
}

    // go: 时间 8 ms, 击败 24.81%; 内存 6.4 MB, 击败 8.99%
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    res := 0
    row, col := len(grid), len(grid[0])
    for r := 0; r < row; r++ {
        for c := 0; c < col; c++ {
            if grid[r][c] == '1' {
                res++
                bfs(grid, r, c)
            }
        }
    }
    return res
}

func bfs(grid [][]byte, r, c int) {
    q := [][]int{{r,c}}
    grid[r][c] = '0'
    row, col := len(grid), len((grid)[0])
    directions := [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        curX := cur[0]
        curY := cur[1]
        for i := 0; i < 4; i++ {
            x := curX + directions[i][0]
            y := curY + directions[i][1]
            if 0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1' {
                q = append(q, []int{x, y})
                grid[x][y] = '0'
            }
        }
    }
}

    // javascript: 时间 80 ms, 击败 58.95%; 内存 49.3 MB, 击败 13.33%
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid.length) {
        return 0;
    }
    let res = 0;
    let row = grid.length, col = grid[0].length;
    for (let r = 0; r < row; ++r) {
        for (let c = 0; c < col; ++c) {
            if (grid[r][c] == '1') {
                ++res;
                bfs(grid, r, c);
            }
        }
    }
    return res;
};

const bfs = function(grid, r, c) {
    const q = [[r,c]];
    grid[r][c] = '0';
    let row = grid.length, col = grid[0].length;
    while (q.length) {
        const cur = q.shift();
        let curX = cur[0];
        let curY = cur[1];
        for (let d of [[-1, 0], [0, -1], [1, 0], [0,1]]) {
            let x = curX + d[0];
            let y = curY + d[1];
            if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                q.push([x,y]);
                grid[x][y] = '0';
            }
        }
    }
}

并查集

  • 建立并查集，遍历矩阵，然后向右向下建立并查集，中间维护并查集的数量

  • 注意中间用了二维转一维，公式为：一维索引=当前行 x 列数 + 当前列

  • 时间复杂度，M、N分别为行数和列数，单次操作的时间复杂度是 ，其中为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 的值不会超过 5，因此也可以看成是常数时间复杂度

  • 空间复杂度 O(MN)

    # python3: 时间 124 ms, 击败 41.96%; 内存 28.2 MB, 击败 17.32%
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        uf = UnionFind(grid)
        row, col = len(grid), len(grid[0])
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '0':
                    continue
                # 往下和右建立并查集
                for x, y in [(r+1, c), (r, c+1)]:
                    if 0 <= x < row and 0 <= y < col and grid[x][y] == '1':
                        uf.unite(r * col + c, x * col + y)
        return uf.getCount()

class UnionFind:
    def __init__(self, grid):
        row, col = len(grid), len(grid[0])
        self.parent = [-1] * (row * col)
        self.count = 0
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '0':
                    continue
                # 初始化，把自身索引赋给自己，此时代表它是并查集的根
                self.parent[r * col + c] = r * col + c
                self.count += 1
    
    def find(self, i):
        # 只要没找到并查集的根会一直找，并把中途节点都赋值为根，可减少后续查询深度
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def unite(self, i, j):
        rooti = self.find(i)
        rootj = self.find(j)
        if rooti == rootj:
            return
        # 此处把rooti值赋给rootj，原因是rooti更小，
        # 可以保持self.parent中同一并查集的都是指向同一个，
        # 更同一，且能减少find次数
        self.parent[rootj] = self.parent[rooti]
        self.count -= 1
    
    def getCount(self):
        return self.count

    // c++: 时间 20 ms, 击败 99.79%; 内存 12.7 MB, 击败 30.16%
class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid) {
        int row = grid.size(), col = grid[0].size();
        parent = vector<int>(row * col, -1);
        count = 0;
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '0') {
                    continue;
                }
                parent[r * col + c] = r * col + c;
                ++count;
            }
        }
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void unite(int i, int j) {
        int rooti = find(i);
        int rootj = find(j);
        if (rooti == rootj) {
            return;
        }
        parent[rootj] = parent[rooti];
        --count;
    }

    int getCount() {
        return count;
    }

private:
    vector<int> parent;
    int count;
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        UnionFind uf(grid);
        int row = grid.size(), col = grid[0].size();
        int directions[2][2] = {{1, 0}, {0, 1}};
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '0') {
                    continue;
                }
                for (int i = 0; i < 2; ++i) {
                    int x = r + directions[i][0];
                    int y = c + directions[i][1];
                    if (0 <= x && x < row && 0 <= y && y < col &&
                        grid[x][y] == '1') {
                        uf.unite(r * col + c, x * col + y);
                    }
                }
            }
        }
        return uf.getCount();
    }
};

    // java: 时间 6 ms, 击败 16.55%; 内存 46.4 MB, 击败 64.27%
class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        UnionFind uf = new UnionFind(grid);
        int row = grid.length, col = grid[0].length;
        int directions[][] = {{1, 0}, {0, 1}};
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '0') {
                    continue;
                }
                for (int i = 0; i < 2; ++i) {
                    int x = r + directions[i][0];
                    int y = c + directions[i][1];
                    if (0 <= x && x < row && 0 <= y && y < col &&
                        grid[x][y] == '1') {
                        uf.unite(r * col + c, x * col + y);
                    }
                }
            }
        }
        return uf.getCount();
    }
}

class UnionFind {
    int[] parent;
    int count;

    public UnionFind(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        parent = new int[row * col];
        count = 0;
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < col; ++c) {
                if (grid[r][c] == '0') {
                    continue;
                }
                parent[r * col + c] = r * col + c;
                ++count;
            }
        }
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    public void unite(int i, int j) {
        int rooti = find(i);
        int rootj = find(j);
        if (rooti == rootj) {
            return;
        }
        parent[rootj] = parent[rooti];
        --count;
    }

    public int getCount() {
        return count;
    }
}

    // go: 时间 8 ms, 击败 24.81%; 内存 4.7 MB, 击败 19.65%
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    uf := NewUnionFind(grid)
    row, col := len(grid), len(grid[0])
    directions := [][]int{{1, 0}, {0, 1}}
    for r := 0; r < row; r++ {
        for c := 0; c < col; c++ {
            if grid[r][c] == '0' {
                continue
            }
            for i := 0; i < 2; i++ {
                x := r + directions[i][0]
                y := c + directions[i][1]
                if 0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1' {
                    uf.Unite(r * col + c, x * col + y)
                }
            }
        }
    }
    return uf.GetCount()
}

type UnionFind struct {
    Parent []int
    Count int
}

func NewUnionFind(grid [][]byte) *UnionFind {
    uf := &UnionFind{
        Count: 0,
    }
    row, col := len(grid), len((grid)[0])
    uf.Parent = make([]int, row * col)
    for r := 0; r < row; r++ {
        for c := 0; c < col; c++ {
            if grid[r][c] == '0' {
                uf.Parent[r * col + c] = -1
            } else {
                uf.Parent[r * col + c] = r * col + c
                uf.Count++
            }
        }
    }
    return uf
}

func (uf *UnionFind)Find(i int) int {
    if uf.Parent[i] != i {
        uf.Parent[i] = uf.Find(uf.Parent[i])
    }
    return uf.Parent[i]
}

func (uf *UnionFind)Unite(i, j int) {
    rooti, rootj := uf.Find(i), uf.Find(j)
    if rooti == rootj {
        return
    }
    uf.Parent[rootj] = uf.Parent[rooti]
    uf.Count--
}

func (uf *UnionFind)GetCount() int {
    return uf.Count
}

    // javascript: 时间 96 ms, 击败 20.30%; 内存 49 MB, 击败 15.23%
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid.length) {
        return 0;
    }
    const uf = new UnionFind(grid);
    let row = grid.length, col = grid[0].length;
    for (let r = 0; r < row; ++r) {
        for (let c = 0; c < col; ++c) {
            if (grid[r][c] == '0') {
                continue;
            }
            for (let d of [[1, 0], [0, 1]]) {
                let x = r + d[0];
                let y = c + d[1];
                if (0 <= x && x < row && 0 <= y && y < col && grid[x][y] == '1') {
                    uf.unite(r * col + c, x * col + y);
                }
            }
        }
    }
    return uf.getCount();
};

class UnionFind {
    constructor(grid) {
        let row = grid.length, col = grid[0].length;
        this.parent = new Array(row * col).fill(-1);
        this.count = 0;
        for (let r = 0; r < row; ++r) {
            for (let c = 0; c < col; ++c) {
                if (grid[r][c] == '0') {
                    continue;
                }
                this.parent[r * col + c] = r * col + c;
                ++this.count;
            }
        }
    }

    find(i) {
        if (this.parent[i] != i) {
            this.parent[i] = this.find(this.parent[i]);
        }
        return this.parent[i];
    }

    unite(i, j) {
        let rooti = this.find(i);
        let rootj = this.find(j);
        if (rooti == rootj) {
            return;
        }
        this.parent[rootj] = this.parent[rooti];
        --this.count;
    }

    getCount() {
        return this.count;
    }
}
Last Updated:
Contributors: Shiqi Lu