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

相关推荐

投递拓竹科技等公司10个岗位
点赞 评论 收藏
分享
07-07 17:06
已编辑
深圳技术大学 golang
点赞 评论 收藏
分享
昨天 10:17
仰恩大学 营销
bg双非,被挂了
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务