LeetCode 305. 岛屿数量 II

Categories:

题目描述
思路分析
1. 解法一：并查集（推荐）
相似题目

题目描述

✅ 305. 岛屿数量 II

思路分析

解法一：并查集（推荐）

核心思路：

每次添加陆地时视作新岛屿，数量加一。

与四邻接陆地合并并减少岛屿数量。

使用并查集维护连通性。

复杂度分析：

时间复杂度：O(k * α(n))，其中 k 表示操作次数。

空间复杂度：O(m * n)，用于并查集。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFind uf = new UnionFind(m * n);
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int count = 0;
        List<Integer> res = new ArrayList<>();

        for (int[] pos : positions) {
            int r = pos[0];
            int c = pos[1];
            int id = r * n + c;
            if (uf.active[id]) {
                res.add(count);
                continue;
            }

            uf.active[id] = true;
            count++;

            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }
                int nid = nr * n + nc;
                if (uf.active[nid] && uf.union(id, nid)) {
                    count--;
                }
            }

            res.add(count);
        }

        return res;
    }

    static class UnionFind {
        int[] parent;
        int[] rank;
        boolean[] active;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            active = new boolean[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

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

        boolean union(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx == ry) {
                return false;
            }
            if (rank[rx] < rank[ry]) {
                parent[rx] = ry;
            } else if (rank[rx] > rank[ry]) {
                parent[ry] = rx;
            } else {
                parent[ry] = rx;
                rank[rx]++;
            }
            return true;
        }
    }
}

func numIslands2(m int, n int, positions [][]int) []int {
	uf := newUnionFind(m * n)
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	count := 0
	res := make([]int, 0, len(positions))

	for _, pos := range positions {
		r, c := pos[0], pos[1]
		id := r*n + c
		if uf.active[id] {
			res = append(res, count)
			continue
		}

		uf.active[id] = true
		count++

		for _, d := range dirs {
			nr, nc := r+d[0], c+d[1]
			if nr < 0 || nr >= m || nc < 0 || nc >= n {
				continue
			}
			nid := nr*n + nc
			if uf.active[nid] && uf.union(id, nid) {
				count--
			}
		}

		res = append(res, count)
	}

	return res
}

type unionFind struct {
	parent []int
	rank   []int
	active []bool
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	active := make([]bool, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	return &unionFind{parent: parent, rank: rank, active: active}
}

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 int, y int) bool {
	rx := uf.find(x)
	ry := uf.find(y)
	if rx == ry {
		return false
	}
	if uf.rank[rx] < uf.rank[ry] {
		uf.parent[rx] = ry
	} else if uf.rank[rx] > uf.rank[ry] {
		uf.parent[ry] = rx
	} else {
		uf.parent[ry] = rx
		uf.rank[rx]++
	}
	return true
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
547. 省份数量	中等	并查集
684. 冗余连接	中等	并查集
721. 账户合并	中等	并查集
803. 打砖块	困难	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/20838108