请教一道面试算法题~
平面上有N个点，求与其余N-1个点距离和（欧式距离，注意，不是平方和）最小的那点坐标。
如果是一维的话，就是排序后的中位数。
平面的话怎么处理呢，除了暴力o（n2）之外，有没有更优的办法
2017-09-22 14:45 已编辑 中国科学技术大学 算法工程师
关注
全部评论
mnf86
浙江大学 安卓
先按x的大小排序，然后通过几何判断出和最大的点只能是第一个点或者最后一个点，比较一下这两个点的距离和，找出和最大的点？
Leoric
南京理工大学 C++
应该是曼哈顿距离吧。 将点按x升序排序，则第k个的点到其它点的x总距离=(k-1)x-sum(1~k-1) + sum(k+1~n)-(n-k)x， 其中sum( i ~ j )为i到j点的x总和（可以用O(1)的复杂度求出）。 然后将点按y升序排序，以类似方法求得每个点到其他点y的总距离。 最后从n个点里挑出x，y总距离最小的。 总时间复杂度为排序的时间复杂度O(nlogn)
SuperBlack
保险职业学院 Java
二维难道不是两个中位数的组合吗？反正x y是互相不影响
端木森
The University of Queensland 科研人员
目测次梯度优化
羡慕会n^2的大佬，我只会O(n^3logn)
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享