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

相关推荐

西松屋:说明原部门有机会把
点赞 评论 收藏
分享
牛客网
牛客企业服务