Number of Islands那道题用Union Find的优点在哪？比起BFS

bfs 解决Number of Islands没问题。但处理Number of IslandsII时间复杂度上好像就比较吃力了。另外，我个人觉得用UnionFind不会忘了怎么做的细节。用dfs或BFS,有时候忘了细节，完蛋啦。

请问uf不会忘了怎么做的细节是指：uf 不用写uf class 的各个细节还是说好写而不会忘记？

我不知道dfs怎么解决，用island1的思路去做超时了。
uf不会忘了是指我记得UnionFind Class怎么写，这部分基本上是直接写出了。

1. class UnionFind{
   
2.         int parents[];
   
3.         
   
4.         public UnionFind(int m, int n){
   
5.             parents = new int[m*n];
   
6.             for(int i = 0; i < m*n;i++){
   
7.                 parents[i] = i;
   
8.             }
   
9.         }
   
10.         
    
11.         public int find(int u){
    
12.             if(u != parents[u]){
    
13.                 parents[u] = find(parents[u]);
    
14.             }
    
15.             return parents[u];
    
16.         }
    
17.         
    
18.         public boolean union(int u, int v){
    
19.             int pu = find(u);
    
20.             int pv = find(v);
    
21.             
    
22.             if(pu == pv){
    
23.                 return false;
    
24.             }
    
25.             
    
26.             parents[pv] = pu;
    
27.             return true;
    
28.         }
    
29.     }

复制代码

上面写出之后，我只需要使用就行，对于新的position，先对count增加1, 向左，上，右，下的顺序判断是否属于同一个父类，如果是的，那么count--。代码我觉得比较容易记。

1. public List<Integer> numIslands2(int m, int n, int[][] positions) {
   
2.         int count = 0;
   
3.         List<Integer> res = new ArrayList<>();
   
4.         UnionFind uf = new UnionFind(m,n);
   
5.         int grid[][] = new int[m][n];
   
6.         
   
7.         if(positions == null || positions.length == 0){
   
8.             return res;
   
9.         }
   
10.         
    
11.         for(int p[]:positions){         
    
12.             grid[p[0]][p[1]] = 1;
    
13.            int curr = n*p[0] + p[1];
    
14. 
    
15.             count++;
    
16.             for(int dir[]:dirs){
    
17.                 int newRow = p[0] + dir[0];
    
18.                 int newCol = p[1] + dir[1];
    
19.                 if(newRow >= 0 && newRow < m && newCol >= 0 && newCol<n && grid[newRow][newCol] ==1){
    
20.                     if(uf.union(n*newRow+newCol, curr)){
    
21.                         count--;
    
22.                     }
    
23. 
    
24.                 }
    
25.             }
    
26.                
    
27.                res.add(count);
    
28.         }
    
29.       
    
30.         return res;
    
31. 
    
32.     }

复制代码

UnionFind 时间复杂度要少，因为只需要跟上下左右的节点比较。

union find的时间复杂度应该是alpha, 当然这个看的是你对子树都做多少操作

这道题经典至极
一定要DFS/BFS/UF都要会做

这类问题的标准做法是BFS（不考虑follow up），甚至它们有一个专门的名字叫flood fill

递归式写法的DFS会爆栈，非递归式的写起来比BFS麻烦
UFS理论时间复杂度更高，多一个alpha(n)因子

cai_lw 发表于 2018-6-14 20:47
这类问题的标准做法是BFS（不考虑follow up），甚至它们有一个专门的名字叫flood fill

递归式写法的DFS ...

可很多时候，尤其单就200 Number of Island这道题来说，DFS的时候我们可以及时把grid[x][y]设置为0；迅速pruning；DFS + pruning最后速度也很快。

一题多解有助于提高你的解题能力。DFS需改变grid的值，所以，有时候可能只能用UF.

这道题经典至极
一定要DFS/BFS/UF都要会做
======================================
同意，UF实在太高频了，还有trie，都是要做到随手能写bug free才行。这俩其实就是一开始掌握麻烦点，只要把属于这个tag的都写一遍想一想就可以知道套路啦，以后写起来就比较顺手了~