请教一道面试算法题~

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

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

相关推荐

行云流水1971:这份实习简历的优化建议: 结构清晰化:拆分 “校园经历”“实习经历” 板块(当前内容混杂),按 “实习→校园→技能” 逻辑排版,求职意向明确为具体岗位(如 “市场 / 运营实习生”)。 经历具象化:现有描述偏流程,需补充 “动作 + 数据”,比如校园活动 “负责宣传” 可加 “运营公众号发布 5 篇推文,阅读量超 2000+,带动 300 + 人参与”;实习内容补充 “协助完成 XX 任务,效率提升 X%”。 岗位匹配度:锚定目标岗位能力,比如申请运营岗,突出 “内容编辑、活动执行” 相关动作;申请市场岗,强化 “资源对接、数据统计” 细节。 信息精简:删减冗余表述(如重复的 “负责”),用短句分点,比如 “策划校园招聘会:联系 10 + 企业,组织 200 + 学生参与,到场率达 85%”。 技能落地:将 “Office、PS” 绑定经历,比如 “用 Excel 整理活动数据,输出 3 份分析表;用 PS 设计 2 张活动海报”,避免技能单独罗列。 优化后需强化 “经历 - 能力 - 岗位需求” 的关联,让实习 / 校园经历的价值更直观。 若需要进一步优化服务,私信
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务