骨骼店面面经顺便问一下约昂赛

第一次发帖，贡献个面经。

点面一道题，给一个矩阵里面有0和1， 问判断是否以1为四个角能组成rectangle。返回是否即可。

给了n^2m^2暴力解和nm^2的set解法。

写了第

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

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

2-8 05:03):
不好意思忘记说了，当时还特意问了一下面试官，面试官意思是只需要考虑以行或列为边的矩形

如果输入矩阵里只有0和1，那么通过对任意两行相加，如果得到的数组含有两个2，是否能证明矩形存在呢？时间复杂度是n^2 或 m^2。

补充内容 (2017-12-6 14:56):
1 0 1 1
1 1 1 0
0 0 1 1
通过对第一行和第二行进行相加，得到2 1 2 1.那么说明[0,0] [0,2] [1,0] [1,2]这四个点可以组成矩形。
只想到几个test case，不知道这个方法有没有bug。。大家可以讨论下。

HOMIE 发表于 2017-12-6 14:53
如果输入矩阵里只有0和1，那么通过对任意两行相加，如果得到的数组含有两个2，是否能证明矩形存在呢？时间 ...

我觉得不行吧，你这样没有考虑对角线的情况，比如说：
0 1 0 1
1 0 1 0
0 1 0 0
这样的话 ［0，1］［1，0］［1，2］［2，1］也能构成一个矩形  

大家看这个思路行不行。
把每行看成二进制数字，所以首先把矩阵转成n个数字的数组，然后每两个数做“与”操作，结果里面有2个1，就说明可以组成矩形。
如果行数多于列数，我们可以改成把每列转成数字，所以总时间复杂度应该是O(m * n)

Lz什么时候面的呀

marcusg 发表于 2017-12-6 04:19
Lz什么时候面的呀

感恩节之前两天。。。。

所以更好的解法应该是 nm(n + m)？

codingsapien 发表于 2017-12-6 04:58
所以更好的解法应该是 nm(n + m)？

对每一行，得到每一对1的列坐标pair，存到set里，遍历行如果有重复就true， complexity是n * m * m。应该会有更好的解法吧。

马克一下 谢谢楼主

多谢lz分享 ~~ 想问问如果用HashMap<Integer, HashSet<Integer>>存的话 key 和value 都分别是什么泥？key 是行吗？

慢慢等。。最近假期多，估计得约到1月份了