请教一道面试算法题~

平面上有N个点,求与其余N-1个点距离和(欧式距离,注意,不是平方和)最小的那点坐标。
如果是一维的话,就是排序后的中位数。
平面的话怎么处理呢,除了暴力o(n2)之外,有没有更优的办法

全部评论
羡慕会n^2的大佬,我只会O(n^3logn)
点赞 回复 分享
发布于 2017-09-22 14:44
目测次梯度优化
点赞 回复 分享
发布于 2017-09-22 14:52
二维难道不是两个中位数的组合吗?反正x y是互相不影响
点赞 回复 分享
发布于 2017-09-22 14:54
    应该是曼哈顿距离吧。          将点按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)
点赞 回复 分享
发布于 2017-09-22 15:20
先按x的大小排序,然后通过几何判断出和最大的点只能是第一个点或者最后一个点,比较一下这两个点的距离和,找出和最大的点?
点赞 回复 分享
发布于 2017-09-22 16:34

相关推荐

9.14一面介绍项目项目中的ETL项目中的拉链表项目中的UDF项目中的Kmeans和DBSCAN八股说一下HDFS说一下进程和线程说一下数据倾斜说一下kafka说一下数仓的建模(雪花,星形,星座)说一下数仓分层的作用OLAP和OLTP的区别说一下数据库三范式手撕两道SQL手写冒泡排序(一面全部答出来了)9.18二面,二面感觉很考验对大数据的理解介绍项目项目中感觉做的最好的地方是哪些介绍一下中国软件杯的比赛你觉得你的项目和比赛在哪些地方体现出了大数据的思路讲讲你对大数据的理解讲讲你对数仓分层的理解讲讲你对数据仓库和数据库的区别的理解数仓和数据库都是SQL Boy, 你对两个SQL Boy的区别的理解有没有用过Doris和clickhouse(没有)说一下LSM Tree说一下Bit Map我看你项目里有lambda框架,讲一下lambda框架说一下Hive中的去重说一下模糊去重(这是真的不会。。。)说一下Kmeans和KNN的区别讲一下Java的集合框架手撕力扣原题,二叉树的层序遍历反问9.23 HR面介绍一下你自己为什么选择大数据你是保研的,你的成绩排名是多少为什么不选择考公或者读博你认为现在公司需要什么样的人才你在秋招的时候是怎么介绍自己的你自己有什么优势(疯狂推销自己,我学习能力强)你说你学习能力强,怎么体现出来的(幸亏我脑子转的快,答上来了)两道场景题1.你入职后,你的师傅负责带你学习,但是刚过了一周,你的师傅被紧急抽调了。这种情况下你如何学习技术。2.入职后,有人得到了晋升,而你没有。但是你感觉你自己的付出不少于他们。你会怎么做。反问9.26 oc #美团求职进展汇总#
点赞 评论 收藏
分享
09-26 16:29
武汉大学 Java
找到工作就狠狠玩CSGO:有机会的,我已经三战美团一面了😂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务