谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 986|回复: 20
收起左侧

[算法题] Number of Islands那道题用Union Find的优点在哪?比起BFS

[复制链接] |试试Instant~ |关注本帖
我的人缘0
shuatizhe 发表于 2018-5-12 21:05:26 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
感觉bfs就很方便,为什么还要用union find,有什么优点吗?节省时间,空间?没看出来

上一篇:刷题打卡
下一篇:reverse linked list 和 Swap Nodes in Pairs的递归写法
我的人缘0
vegito2002 发表于 2018-5-13 01:32:03 | 显示全部楼层
  此人我要顶:
 
49% (13) 【我投】
  此人我要踩:
 
51% (15) 【我投】
题目本身UF是没有优点. 但是比如假如给你一个Follow-Up: land cell是一个stream不断出现的, 这个时候UF这题就有价值了. 反正多掌握一个方法没有坏处, UF其实还是出场率比较高的一个算法.
回复 支持 2 反对 0

使用道具 举报

全球28万学生4.7分推荐
我的人缘2
pxu 发表于 2018-5-24 09:34:10 | 显示全部楼层
  此人我要顶:
 
73% (41) 【我投】
  此人我要踩:
 
27% (15) 【我投】
bfs 解决Number of Islands没问题。但处理Number of IslandsII时间复杂度上好像就比较吃力了。另外,我个人觉得用UnionFind不会忘了怎么做的细节。用dfs或BFS,有时候忘了细节,完蛋啦。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
buranmilk4 发表于 2018-5-13 02:27:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
一,前面的同学说得对,第二题的话用UF比较好做;二,UF是一种解题思想,适用于这种找集群的题目,不能说BFS不好,但是从这道题目的名字上来讲UF更符合,只是恰巧题目本身用BFS/DFS更加简洁明了
回复 支持 1 反对 0

使用道具 举报

我的人缘2
pxu 发表于 2018-5-12 22:53:03 | 显示全部楼层
  此人我要顶:
 
73% (41) 【我投】
  此人我要踩:
 
27% (15) 【我投】
Number of island I 就是我用bsf 实现的。island II 不知道能不能只用bsf实现
回复 支持 反对

使用道具 举报

我的人缘0
eason0218 发表于 2018-5-13 08:00:56 | 显示全部楼层
  此人我要顶:
 
25% (1) 【我投】
  此人我要踩:
 
75% (3) 【我投】
试试Number of Island 2,你就知道用union find有什么好处了。。。
回复 支持 反对

使用道具 举报

我的人缘0
2006reload 发表于 2018-5-13 13:06:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
union find会省时间如果一直query
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| shuatizhe 发表于 2018-5-14 11:13:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
用bfs和UF的时间和空间复杂度分别是多少?
回复 支持 反对

使用道具 举报

我的人缘0
hotinherre 发表于 2018-5-14 12:46:18 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
uf 适合动态生成集合。 bfs dfs 都是对已知数据的遍历
回复 支持 反对

使用道具 举报

我的人缘0
阿钟 发表于 2018-5-14 12:47:32 来自手机 | 显示全部楼层
  此人我要顶:
 
33% (0) 【我投】
  此人我要踩:
 
67% (3) 【我投】
同楼上,BFS/DFS感觉就是不大能retain information
回复 支持 反对

使用道具 举报

我的人缘0
oio14644 发表于 2018-5-15 07:55:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
不是说uf 优点在哪儿,而是有的面试官指定你用uf写,bsf 写的再6, 又如何
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| shuatizhe 发表于 2018-5-25 23:09:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问uf不会忘了怎么做的细节是指:uf 不用写uf class 的各个细节还是说好写而不会忘记?
回复 支持 反对

使用道具 举报

我的人缘2
pxu 发表于 2018-6-11 10:59:19 | 显示全部楼层
  此人我要顶:
 
73% (41) 【我投】
  此人我要踩:
 
27% (15) 【我投】
我不知道dfs怎么解决,用island1的思路去做超时了。
uf不会忘了是指我记得UnionFind Class怎么写,这部分基本上是直接写出了。
[Java] 纯文本查看 复制代码
 class UnionFind{
        int parents[];
        
        public UnionFind(int m, int n){
            parents = new int[m*n];
            for(int i = 0; i < m*n;i++){
                parents[i] = i;
            }
        }
        
        public int find(int u){
            if(u != parents[u]){
                parents[u] = find(parents[u]);
            }
            return parents[u];
        }
        
        public boolean union(int u, int v){
            int pu = find(u);
            int pv = find(v);
            
            if(pu == pv){
                return false;
            }
            
            parents[pv] = pu;
            return true;
        }
    }



上面写出之后,我只需要使用就行,对于新的position,先对count增加1, 向左,上,右,下的顺序判断是否属于同一个父类,如果是的,那么count--。代码我觉得比较容易记。
[Java] 纯文本查看 复制代码
public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int count = 0;
        List<Integer> res = new ArrayList<>();
        UnionFind uf = new UnionFind(m,n);
        int grid[][] = new int[m][n];
        
        if(positions == null || positions.length == 0){
            return res;
        }
        
        for(int p[]:positions){         
            grid[p[0]][p[1]] = 1;
           int curr = n*p[0] + p[1]; 

            count++;
            for(int dir[]:dirs){
                int newRow = p[0] + dir[0];
                int newCol = p[1] + dir[1];
                if(newRow >= 0 && newRow < m && newCol >= 0 && newCol<n && grid[newRow][newCol] ==1){
                    if(uf.union(n*newRow+newCol, curr)){
                        count--;
                    }

                }
            }
               
               res.add(count); 
        }
       
        return res;

    }



回复 支持 反对

使用道具 举报

我的人缘2
pxu 发表于 2018-6-11 11:02:37 | 显示全部楼层
  此人我要顶:
 
73% (41) 【我投】
  此人我要踩:
 
27% (15) 【我投】
UnionFind 时间复杂度要少,因为只需要跟上下左右的节点比较。
回复 支持 反对

使用道具 举报

我的人缘0
肥宅快乐水 发表于 2018-6-12 11:22:10 | 显示全部楼层
  此人我要顶:
 
52% (9) 【我投】
  此人我要踩:
 
48% (8) 【我投】
union find的时间复杂度应该是alpha, 当然这个看的是你对子树都做多少操作
回复 支持 反对

使用道具 举报

我的人缘0
biomedicineman 发表于 2018-6-14 16:49:47 | 显示全部楼层
  此人我要顶:
 
25% (45) 【我投】
  此人我要踩:
 
75% (134) 【我投】
这道题经典至极
一定要DFS/BFS/UF都要会做
回复 支持 反对

使用道具 举报

我的人缘0
cai_lw 发表于 2018-6-14 20:47:29 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这类问题的标准做法是BFS(不考虑follow up),甚至它们有一个专门的名字叫flood fill

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

使用道具 举报

我的人缘0
biomedicineman 发表于 2018-6-15 06:47:18 | 显示全部楼层
  此人我要顶:
 
25% (45) 【我投】
  此人我要踩:
 
75% (134) 【我投】
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最后速度也很快。
回复 支持 反对

使用道具 举报

我的人缘2
pxu 发表于 2018-6-15 07:36:19 | 显示全部楼层
  此人我要顶:
 
73% (41) 【我投】
  此人我要踩:
 
27% (15) 【我投】
一题多解有助于提高你的解题能力。DFS需改变grid的值,所以,有时候可能只能用UF.
回复 支持 反对

使用道具 举报

我的人缘0
martinliu2218 发表于 2018-6-15 11:47:19 | 显示全部楼层
  此人我要顶:
 
60% (6) 【我投】
  此人我要踩:
 
40% (4) 【我投】

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html






手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-24 17:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表