R******5
发帖数: 10 | 1 大家好，
最近onsite了一家公司， 被问到一道经典得number of islands题， 就是给一个二维
01矩阵， 求数出有多少个island。时间复杂度O(mn), 空间复杂度O(1). 也就是说不能
用BFS和DFS。而且island得shape是任意的。 当时实在拿这题没办法。后来回来去网上
搜了下， 也没找到好的方法， 所以到论坛来求助， 希望知道的朋友指点下迷津， 谢
谢了。 |
h*********n
发帖数: 11319 | 2 空间复杂度一般不算递归本身的overhead。
在这个前提下，DFS就是O(mn) + O(1).
【在 R******5 的大作中提到】
: 大家好，
: 最近onsite了一家公司， 被问到一道经典得number of islands题， 就是给一个二维
: 01矩阵， 求数出有多少个island。时间复杂度O(mn), 空间复杂度O(1). 也就是说不能
: 用BFS和DFS。而且island得shape是任意的。 当时实在拿这题没办法。后来回来去网上
: 搜了下， 也没找到好的方法， 所以到论坛来求助， 希望知道的朋友指点下迷津， 谢
: 谢了。
|
z*********n
发帖数: 1451 | 3 面试官专门说了不许BFS和DFS吗？这么奇葩的要求？还是题目有变化你没注意到。 |
t****b
发帖数: 2484 | 4 这个明显就是dfs吧
楼主面的时候被告知dfs 不行？ |
R******5
发帖数: 10 | 5 真的是面试官说了不能用BFS和DFS， 不能用extra space。他给我的提示是，如果
matrix只有一层，则可以用个counter解决， 如果matrix多层，而shape是rectangle也
是可以用一个counter解决， 现在问题是拓展到shape为任意连着的shape， 算法该怎
么改可以解决这个问题。然后我有给出反例， 但他说可以考虑减counter。但我还是不
知道这样做是否能解决所有case。在网上搜了一些帖子，基本都是用BFS和DFS的，或者
变形。 实在没办法才上来求助。
不知道是否有大神知道这个算法存在， 还是说我被这个韩国小哥给黑了。。。 |
z*******o
发帖数: 4773 | 6 好像真可以,
在原来矩阵上直接改,设id标志,
下一行计数时查和上一行是否连接,根据id还可以合并.
【在 R******5 的大作中提到】
: 真的是面试官说了不能用BFS和DFS， 不能用extra space。他给我的提示是，如果
: matrix只有一层，则可以用个counter解决， 如果matrix多层，而shape是rectangle也
: 是可以用一个counter解决， 现在问题是拓展到shape为任意连着的shape， 算法该怎
: 么改可以解决这个问题。然后我有给出反例， 但他说可以考虑减counter。但我还是不
: 知道这样做是否能解决所有case。在网上搜了一些帖子，基本都是用BFS和DFS的，或者
: 变形。 实在没办法才上来求助。
: 不知道是否有大神知道这个算法存在， 还是说我被这个韩国小哥给黑了。。。
|
u***n
发帖数: 21026 | |
D**********0
发帖数: 1022 | |
s**********g
发帖数: 14942 | 9 union find不需要额外space存root？
【在 D**********0 的大作中提到】
: Union Find.
: 这都是原题。
|
z*********n
发帖数: 1451 | 10
这不是原题。。起码我是第一次听说number of island要求这么解的。。
个人感觉面试官提示的想法也无法做到O(1)space，至少需要记录一下哪几个id合并了。
版上的街霸帮搞Poj的人呢？赶快现身帮lz解惑，需要你们的时候到了。
【在 D**********0 的大作中提到】
: Union Find.
: 这都是原题。
|
D**********0
发帖数: 1022 | 11 那就不知道了，等大神来解。
了。
【在 z*********n 的大作中提到】
:
: 这不是原题。。起码我是第一次听说number of island要求这么解的。。
: 个人感觉面试官提示的想法也无法做到O(1)space，至少需要记录一下哪几个id合并了。
: 版上的街霸帮搞Poj的人呢？赶快现身帮lz解惑，需要你们的时候到了。
|
R******5
发帖数: 10 | 12 嗯， 我也这么觉得， 起码像以下这种case：
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
你不mapping区分下各个island的话， 到最后一行没法判断该不该减。我也是实在不知
道怎么解这题，我面试时都说了BFS和union find 的方法， 但面试官说不是他想要的
， 他觉得按照他提示得方法用counter就可以O(mn) 时间复杂度和O(1)空间复杂度解出
这题。
了。
【在 z*********n 的大作中提到】
:
: 这不是原题。。起码我是第一次听说number of island要求这么解的。。
: 个人感觉面试官提示的想法也无法做到O(1)space，至少需要记录一下哪几个id合并了。
: 版上的街霸帮搞Poj的人呢？赶快现身帮lz解惑，需要你们的时候到了。
|
z*******o
发帖数: 4773 | 13 我有个idea:
就是给每个为1的element设一个值: i*cols+j+2
凡是有连接的:从上至下,从下到上,从左到右,从右到左,四个方向, populate该岛中最
小值.
再遍历matrix,
if matrix[i][j]==i*cols+j+2: cnt+=1
写起来太麻烦 |
z*******o
发帖数: 4773 | |
