Leetcode - Number of Islands II

My code:

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

public class Solution {
    
    private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> ret = new ArrayList<Integer>();
        if (m <= 0 || n <= 0) {
            return ret;
        }
        
        UnionFind uf = new UnionFind(m, n);
        for (int i = 0; i < positions.length; i++) {
            int x = positions[i][0];
            int y = positions[i][1];
            int id = uf.add(x, y);
            for (int j = 0; j < 4; j++) {
                int neib_x = x + dir[j][0];
                int neib_y = y + dir[j][1];
                
                int neib_id = uf.getId(neib_x, neib_y);
                if (neib_id > 0 && neib_id != id) {
                    uf.union(neib_id, id);
                }
            }
            ret.add(uf.getCounter());
        }
        
        return ret;
    }
}


class UnionFind {
    private int[] ids;
    private int[] sz;
    private int counter = 0;
    private int m;
    private int n;
    UnionFind(int m, int n) {
        ids = new int[m * n + 1];
        sz = new int[m * n + 1];
        this.m = m;
        this.n = n;
    }
    
    public int add(int i, int j) {
        int index = indexOf(i, j);
        ids[index] = index;
        sz[index] = 1;
        counter++;
        return index;
    }
    
    public int indexOf(int i, int j) {
        return i * n + j + 1;
    }
    
    public int getId(int i, int j) {
        if (0 <= i && i < m && 0 <= j && j < n) {
            return ids[indexOf(i, j)];
        }
        else {
            return 0;
        }
    }
    
    public int find(int i) {
        if (ids[i] == i) {
            return i;
        }
        else {
            int ret = find(ids[i]);
            ids[i] = ret;
            return ret;
        }
    }
    
    public void union(int i, int j) {
        int id1 = find(i);
        int id2 = find(j);
        if (id1 == id2) {
            return;
        }
        else {
            counter--;
            if (sz[i] > sz[j]) {
                ids[id2] = id1;
                sz[i] += sz[j];
            }
            else {
                ids[id1] = id2;
                sz[j] += sz[i];
            }
        }
    }
    
    public int getCounter() {
        return this.counter;
    }
}

reference:
https://discuss.leetcode.com/topic/29518/java-python-clear-solution-with-unionfind-class-weighting-and-path-compression

我也打算用 Union Find 来写。但是我的 Union Find 并不是正规的Union Find, 思想是有了，但是有些细节并没能实现。

比如， Number of Islands I, 最后要求岛屿的个数。
我需要遍历一遍ids[], 找出 unique id 的个数。

但是，正宗的UF， O(1) 时间就可以返回。

新建一个新类，叫做 UF

然后有个 counter
每次 add操作的时候， counter++;
每次 union 操作的时候，如果传入的 i, j id不同，那么 counter--

有了这个就好办了。
还有个问题是，用什么表示，这个地方是水，还是岛屿
还需要再新建一个2d array吗？
不用了。 id = 0,都是水。
id = [ 1 , m * n ] 都是islands

所以，每次把一处变成island的时候，
先 add(), 拿到他的id，这时候在底层， counter 自动加 1
然后看他四周，询问他们的id，如果他们的 id > 0 && their id != id
就 union 一下。这时候在底层， counter自动减去 1

最后返回 counter 个数。

time complexity: k log(m * n)
这是不考虑初始化数组的复杂度
之后的每次操作，都是 find + union 的组合，所以是 log(m * n)

Anyway, Good luck, Richardo! -- 09/22/2016

Leetcode - Number of Islands II

推荐阅读更多精彩内容