fb店面新鲜跪经

这个follow up思路基本就这么做 但是写code起来还是挺费劲

hychin 发表于 2017-11-17 11:58
good point 这下你彻底会了

全靠大腿执教啊

adrianliu729 发表于 2017-11-17 08:59
这是很多公司的面经题，被FB抄下来了。。。先锁定对角线两个点，找其他两个点在不在set里面。

不用这么麻烦，就按照x coordinates hash
y coordinates hash
就好
其实任意俩个垂直别，和任意两个水平边就可以组成矩形

补充内容 (2017-11-17 14:09):
举例子： （0,10）(0,20) (0,30) (1,10) (1,20) (1,40)
可以hash x-coordinates map : <0, {10,20,30}> <1,(10,20,40)>
可以在用another hash y-coor 或者直接看 （10,20,30）和 （10，20，40）有没有交集有两个元素

edyyy 发表于 2017-11-17 13:51
不用这么麻烦，就按照x coordinates hash
y coordinates hash
就好

不是不可行，只是复杂度不见得低，你这个两两x 匹配找到两两x 之后再找两个交集y至少在需要N，一共用N^3..  对角线法 两两点 pair N^2,直接可以找到对应的两个点是否在已有的里面只需要N^2.  而且你的办法也没法解决非平行于X轴的情况

hychin 发表于 2017-11-17 14:18
不是不可行，只是复杂度不见得低，你这个两两x 匹配找到两两x 之后再找两个交集y至少在需要N，一共用N^3. ...

n^2 找到两个对角点pair， 然后判断对应的另两个对角点，在不在x coordinates hash
y coordinates hash

hychin 发表于 2017-11-17 14:18
不是不可行，只是复杂度不见得低，你这个两两x 匹配找到两两x 之后再找两个交集y至少在需要N，一共用N^3. ...

题目不是说要平行于坐标轴