fb新鲜面经

发面经攒人品第一轮 离原点最近k个点 做完了问了楼主如果有又一个新的点xy 不是原点 要求再原先空间基础上不能再用多余的空间存d

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

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

ing 2毛体扑来string 跑了tescase
求过赞人品求过

zbyxhg 发表于 2017-12-4 10:14
不是这个意思的，是要求那些所有点到这个新点的最近的k个点

X和Y分开存，怕是说的Kd tree吧？

沙发！谢谢楼主，祝顺利！

感谢分享，祝好运！

楼主现在知道咋算那个followup了吗

第一题什么意思啊？楼主可以再解释一下吗？

dunan00001 发表于 2017-12-3 06:05
楼主现在知道咋算那个followup了吗

还是没想清楚。。。求地里大神指点啊

luka77 发表于 2017-12-3 07:05
第一题什么意思啊？楼主可以再解释一下吗？

就是新给你一个点，不是原点，还是求最近的k个点，但是要求你要在原来结果的基础上算，不花费新的空间存距离，楼主只想到了用三角形两边求第三边的方法更新距离，要更新一遍时间要O(n), 面试官要求时间复杂度更好。我还是没想出来

zbyxhg 发表于 2017-12-4 10:05
就是新给你一个点，不是原点，还是求最近的k个点，但是要求你要在原来结果的基础上算，不花费新的空间存 ...

如果我没理解错的话，直接算出新的点到原点的距离，然后和第k个点比较，取更近的一个不就好了？常数时间复杂度

luka77 发表于 2017-12-4 10:10
如果我没理解错的话，直接算出新的点到原点的距离，然后和第k个点比较，取更近的一个不就好了？常数时间 ...

不是这个意思的，是要求那些所有点到这个新点的最近的k个点