脸家实习电面挂经

游客 242.21.245.x 发表于 2020-11-23 09:42
我当时想到的就是选任意两个点作为左上角和右下角的点确定一个矩形, 这一步复杂度是n ^2。然后在所有的点 ...

哦哦。矩形的边一定是平行于坐标轴吗？否则就不能根据两个点确定其他点了吧？

yiliaobailiao 发表于 2020-11-23 13:07
哦哦。矩形的边一定是平行于坐标轴吗？否则就不能根据两个点确定其他点了吧？

我忘了当时题干有没有提到平行于坐标轴了，不过当时没考虑这个情况。。。那有什么好的思路吗

如果把相同的x或者y放到一个set里面，这个是假设平行于x或者y轴吗？ 我的思路是两层的Map，一层的key是边长，第二层的key是斜率。。这样应该是O(n2)

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

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

tachy_9 发表于 2020-11-24 16:48
第一题，如果仅按照你的描述的话（找出一堆点里是否存在能组成矩形的四个点），那你的方法是不work的，因为 ...

BTW，找符合条件的线段这个部分有点类似于3 Sum，用个Hash Map存已经找过的，然后在新的里面找有没有符合条件的

tachy_9 发表于 2020-11-24 16:48
第一题，如果仅按照你的描述的话（找出一堆点里是否存在能组成矩形的四个点），那你的方法是不work的，因为 ...

嗯嗯，谢谢！

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

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

yiliaobailiao 发表于 2020-11-25 12:38
我记得LC有一道题是找长方形的个数，具体题号没有找到。。。有一种O(N^3)的解法，大意思三层循环，可以通 ...

蠡口 九流三 有点类似。求所有点组成的最小矩形面积，不一定跟数轴平行。

hername 发表于 2020-11-26 19:17
蠡口 九流三 有点类似。求所有点组成的最小矩形面积，不一定跟数轴平行。

没错！就是这个题。原来是有O(N^2)的解法