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 來(lái)寫(xiě)。但是我的 Union Find 并不是正規(guī)的Union Find, 思想是有了，但是有些細(xì)節(jié)并沒(méi)能實(shí)現(xiàn)。

比如， Number of Islands I, 最后要求島嶼的個(gè)數(shù)。
我需要遍歷一遍ids[], 找出 unique id 的個(gè)數(shù)。

但是，正宗的UF， O(1) 時(shí)間就可以返回。

新建一個(gè)新類(lèi)，叫做 UF

然后有個(gè) counter
每次 add操作的時(shí)候， counter++;
每次 union 操作的時(shí)候， 如果傳入的 i, j id不同，那么 counter--

有了這個(gè)就好辦了。
還有個(gè)問(wèn)題是，用什么表示，這個(gè)地方是水，還是島嶼
還需要再新建一個(gè)2d array嗎？
不用了。 id = 0,都是水。
id = [ 1 , m * n ] 都是islands

所以，每次把一處變成island的時(shí)候，
先 add(), 拿到他的id，這時(shí)候在底層， counter 自動(dòng)加 1
然后看他四周，詢(xún)問(wèn)他們的id，如果 他們的 id > 0 && their id != id
就 union 一下。這時(shí)候在底層， counter自動(dòng)減去 1

最后返回 counter 個(gè)數(shù)。

time complexity: k log(m * n)
這是不考慮初始化數(shù)組的復(fù)雜度
之后的每次操作，都是 find + union 的組合，所以是 log(m * n)

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