求问M家面试题

被面了一道题目:
一个二维数组， 1代表陆地，0代表水，里面有且只有一块陆地，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我没有什么思路, 挂了, 大家帮我想想?

两个指针一个从左上往右下扫，另一个从右下往左上扫，遇到的第一个1就是要找的点。这样是m*n的复杂度。其实也可以用binary search，找两个边界。followup没有明白什么意思，只有一块陆地的话，其他不就一块水吗？

lfzh123 发表于 2017-4-5 01:37
两个指针一个从左上往右下扫，另一个从右下往左上扫，遇到的第一个1就是要找的点。这样是m*n的复杂度。其实 ...

多谢指点. Follow up 是这么说的:

huangyingw 发表于 2017-4-5 02:04
多谢指点. Follow up 是这么说的:

刚才按错键了,
In a matrix of 1 and 0s, return all unique groups of 0s and their sizes. Assuming all groups of 0s are rectangles  

这题是jet面试经典题啊

33847682 发表于 2017-4-5 02:50
这题是jet面试经典题啊

求思路 , 求指点.

如果用二分，私下认为这题和 leetcode 302 Smallest Rectangle Enclosing Black Pixels 比较像
可以先找左右边界，所以，对col index进行二分(O(logN))，每个iteration里面检查col index上所有row (O(N))是不是有1的情况，有则说明col index在陆地范围内，跟新col index直到找到 左/右边界。
类似可以找上下边界，当然知道了左右边界后，你也可以暴力扫一遍找上下边界，因为题目说了陆地是方的。
时间复杂度是O(N * logN)

huangyingw 发表于 2017-4-5 02:04
刚才按错键了,
In a matrix of 1 and 0s, return all unique groups of 0s and their sizes. Assuming  ...

follow up 不能用BFS 解吗?

huangyingw 发表于 2017-4-5 04:00
求思路 , 求指点.

第一问的话 就很容易 start=0  end= m*n -1 做二分 只要找到一个为1的点就可以了 然后在这个点往上下左右做二分 就能求出坐标了
followup的话 我觉得用union find就可以了 最简便