LeetCode 第305题：岛屿数量 II

📖 文章摘要

本文详细解析LeetCode第305题“岛屿数量 II”，这是一道考察并查集和动态连通性的困难难度题目。文章提供了并查集的实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习并查集和动态连通性问题的读者。

核心知识点： 并查集、动态连通性、矩阵处理
难度等级： 困难
推荐人群： 具备基础算法知识，想要提升并查集和图论处理能力的开发者

题目描述

给你一个大小为 m x n 的二维网格 grid 和一个数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 次操作将单元格 (ri, ci) 的状态更改为 1 （陆地）。一开始，grid 中的所有单元格都是 0 （水）。

返回一个数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 的状态更改为 1 后的岛屿数量。

岛屿的定义如下：

岛屿是由相邻的陆地单元格组成的区域，这里的「相邻」要求两个单元格共享边。
你可以假设 grid 的四个边缘都被 0（水）包围。

示例

示例 1：

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 grid 被全部注入水。（0 代表水，1 代表陆地）
- 操作 #1：positions[0] = [0,0] 将 grid[0][0] 的水变为陆地。岛屿的数量为 1。
- 操作 #2：positions[1] = [0,1] 将 grid[0][1] 的水变为陆地。岛屿的数量仍然为 1。
- 操作 #3：positions[2] = [1,2] 将 grid[1][2] 的水变为陆地。岛屿的数量变为 2。
- 操作 #4：positions[3] = [2,1] 将 grid[2][1] 的水变为陆地。岛屿的数量变为 3。

示例 2：

输入：m = 1, n = 1, positions = [[0,0]]
输出：[1]

提示

1 <= m, n <= 10^4
1 <= positions.length <= 10^4
positions[i].length == 2
0 <= ri < m
0 <= ci < n

解题思路

本题使用并查集（Union-Find）数据结构来解决：

初始化：
- 创建并查集数据结构
- 记录已添加的陆地
- 初始化岛屿数量为0
处理每个操作：
- 将新的陆地加入并查集
- 检查四个方向的相邻单元格
- 如果相邻单元格是陆地，则合并
- 更新岛屿数量
优化技巧：
- 使用路径压缩
- 使用按秩合并
- 使用方向数组简化代码

图解思路

并查集操作分析表

操作	时间复杂度	作用	优化方式
Find	O(α(n))	查找根节点	路径压缩
Union	O(α(n))	合并集合	按秩合并
Add	O(1)	添加新节点	-
Count	O(1)	获取集合数量	-

方向数组使用表

方向	行偏移	列偏移	用途
上	-1	0	检查上方相邻
下	1	0	检查下方相邻
左	0	-1	检查左方相邻
右	0	1	检查右方相邻

代码实现

C# 实现

public class Solution {
    private int[] parent;
    private int[] rank;
    private int count;
    private bool[,] grid;
    private readonly int[][] directions = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0},
        new int[] {0, -1}, new int[] {0, 1}
    };
    
    public IList<int> NumIslands2(int m, int n, int[][] positions) {
        parent = new int[m * n];
        rank = new int[m * n];
        grid = new bool[m, n];
        count = 0;
        
        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
        }
        
        var result = new List<int>();
        
        foreach (var pos in positions) {
            int r = pos[0], c = pos[1];
            if (grid[r, c]) {
                result.Add(count);
                continue;
            }
            
            grid[r, c] = true;
            int index = r * n + c;
            count++;
            
            foreach (var dir in directions) {
                int newR = r + dir[0];
                int newC = c + dir[1];
                
                if (newR >= 0 && newR < m && newC >= 0 && newC < n && grid[newR, newC]) {
                    Union(index, newR * n + newC);
                }
            }
            
            result.Add(count);
        }
        
        return result;
    }
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    private void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
}

Python 实现

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.count = 0
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                rootX, rootY = rootY, rootX
            self.parent[rootY] = rootX
            if self.rank[rootX] == self.rank[rootY]:
                self.rank[rootX] += 1
            self.count -= 1

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        uf = UnionFind(m * n)
        grid = set()
        result = []
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for r, c in positions:
            if (r, c) in grid:
                result.append(uf.count)
                continue
                
            grid.add((r, c))
            index = r * n + c
            uf.count += 1
            
            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if (newR, newC) in grid:
                    uf.union(index, newR * n + newC)
            
            result.append(uf.count)
            
        return result

C++ 实现

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;
    
public:
    UnionFind(int size) : parent(size), rank(size, 0), count(0) {
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            count--;
        }
    }
    
    void addIsland() { count++; }
    int getCount() const { return count; }
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        UnionFind uf(m * n);
        vector<vector<bool>> grid(m, vector<bool>(n, false));
        vector<int> result;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (const auto& pos : positions) {
            int r = pos[0], c = pos[1];
            if (grid[r][c]) {
                result.push_back(uf.getCount());
                continue;
            }
            
            grid[r][c] = true;
            int index = r * n + c;
            uf.addIsland();
            
            for (const auto& dir : directions) {
                int newR = r + dir.first;
                int newC = c + dir.second;
                
                if (newR >= 0 && newR < m && newC >= 0 && newC < n && grid[newR][newC]) {
                    uf.unite(index, newR * n + newC);
                }
            }
            
            result.push_back(uf.getCount());
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：248 ms
内存消耗：52.6 MB

Python 实现

执行用时：196 ms
内存消耗：18.4 MB

C++ 实现

执行用时：88 ms
内存消耗：28.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	248 ms	52.6 MB	实现清晰，性能适中
Python	196 ms	18.4 MB	代码简洁，内存占用小
C++	88 ms	28.2 MB	性能最优，内存适中

代码亮点

🎯 使用并查集优化连通性判断
💡 路径压缩和按秩合并优化
🔍 方向数组简化代码
🎨 面向对象设计清晰

常见错误分析

🚫 并查集初始化错误
🚫 边界条件处理不当
🚫 重复位置处理错误
🚫 连通性判断错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS/BFS	O(k*mn)	O(mn)	直观易懂	效率低
并查集	O(k*α(mn))	O(mn)	效率高	实现复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第305题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

并查集操作分析表

方向数组使用表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流