leetcode | 305. Number of Islands II (并查集)

最新推荐文章于 2021-11-30 06:01:53 发布

一的三次方

最新推荐文章于 2021-11-30 06:01:53 发布

阅读量436

点赞数

分类专栏： leetcode

本文链接：https://blog.csdn.net/mike_learns_to_rock/article/details/88629179

版权

leetcode 专栏收录该内容

69 篇文章

订阅专栏

这篇博客探讨了LeetCode第305题——Number of Islands II，分析了为什么DFS和BFS不适合处理动态连通问题，并详细介绍了使用并查集（Union-Find）算法在O(k * log mn)的时间复杂度内求解该问题，其中k代表操作位置的长度，空间复杂度为O(m * n)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]

题目描述：m*n的网格区域，刚开始都是水，addLand操作会把某个区域变成陆地；动态求出所有addLand操作后的陆地连通区域数量；

分析

DFS/BFS不适合处理动态连通问题; 如下UF解法-时间均摊复杂度非常接近O(k) ，时间复杂度O(k * log mn)k代表posotions的长度，空间复杂度为O(m * n)

解法

class Solution {
    class UnionFind {
        private int union[];
        private int rank[];
        private int size = 0;
        
        public UnionFind(int n) {
            union = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                union[i] = -1;
            }
        }
        
        private int find(int i) {
            while (i != union[i]) i = union[i];
            return i;
        }
        
        public void union(int x, int y) {
            if (union[x] == -1 || union[y] == -1) return;
            int rootx = find(x);
            int rooty = find(y);
            if (rootx == rooty) return;
            if (rank[rootx] > rank[rooty]) {
                union[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                union[rootx] = rooty;
            } else {
                union[rooty] = rootx;
                rank[rootx]++;
            }
            size--;
        }
        
        public void add(int i) {
            if (union[i] == -1) {
                union[i] = i;
                size++;
            }
        }
        
        public int getSize() {
            return size;
        }
    }
    
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        if (m <= 0 || n <= 0) return new ArrayList<Integer>();
        UnionFind uf = new UnionFind(m * n);
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < positions.length; i++) {
            int r = positions[i][0];
            int c = positions[i][1];
            // assuming r and c are valid
            uf.add(r * n + c);
            if (r > 0) uf.union(r * n + c, (r - 1) * n + c);
            if (r < m - 1) uf.union(r * n + c, (r + 1) * n + c);
            if (c > 0) uf.union(r * n + c, r * n + (c - 1));
            if (c < n - 1) uf.union(r * n + c, r * n + (c + 1));
            res.add(uf.getSize());
        }
        return res;
    }
}