应该是曼哈顿距离吧。          将点按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)
点赞 2

相关推荐

点赞 评论 收藏
分享
有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司7个岗位
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务