首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
々炫天空/yiw
2017-09-22 14:45
已编辑
中国科学技术大学 算法工程师
关注
已关注
取消关注
请教一道面试算法题~
平面上有N个点,求与其余N-1个点距离和(欧式距离,注意,不是平方和)最小的那点坐标。
如果是一维的话,就是排序后的中位数。
平面的话怎么处理呢,除了暴力o(n2)之外,有没有更优的办法
提示
全部评论
推荐
最新
楼层
mnf86
浙江大学 安卓
先按x的大小排序,然后通过几何判断出和最大的点只能是第一个点或者最后一个点,比较一下这两个点的距离和,找出和最大的点?
点赞
回复
分享
发布于 2017-09-22 16:34
Leoric
南京理工大学 C++
应该是曼哈顿距离吧。 将点按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
SuperBlack
保险职业学院 Java
二维难道不是两个中位数的组合吗?反正x y是互相不影响
点赞
回复
分享
发布于 2017-09-22 14:54
端木森
The University of Queensland 科研人员
目测次梯度优化
点赞
回复
分享
发布于 2017-09-22 14:52
已删除
羡慕会n^2的大佬,我只会O(n^3logn)
点赞
回复
分享
发布于 2017-09-22 14:44
暂无评论,快来抢首评~
相关推荐
07-22 14:54
门头沟学院 客户端其它
DeepSeek和百度二选一
如题,DeepSeek和百度二选一,你会选择哪个,那么好,发起投票 我是不管 百度 还是 DeepSeek 现在都很少用,工作中用的开发Ai工具是Trae和Cursor这两个,其中Trae用的比较多,最恐怖的是,现在公司已经半强制性让使用Ai进行编程,以此提升效率了,很多客户端的UI页面,直接把视觉提供的稿子给Trae,它就可以直接生成对应的布局文件了,客户端还不像后端那样,像我开发一个新需求,基本上UI界面都是自己写布局文件,现在可倒好,Trae直接解决了,我真是靠北了。除了直接绘制UI,它还能根据你现有的项目框架,直接新增功能,但是还不是那么特别厉害吧,要不然程序员真失业了,但是新人使用工...
《有啥说啥》栏目
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
07-25 17:26
终于有大厂实习offer了
点赞
评论
收藏
分享
07-02 22:46
门头沟学院 Java
先发制人这一块
码农索隆:
hr:“管你投没投,先挂了再说”
点赞
评论
收藏
分享
07-24 17:14
腾讯音乐娱乐集团_客户端(准入职员工)
在工位偶遇汪苏泷
公司停摆一小时 大明星的排面
职场新人体验
点赞
评论
收藏
分享
07-25 18:15
门头沟学院 前端工程师
26届校招提前批影石insta 360
投递岗位不透露了,直接投递等笔试了,最多可以投三个
投递影石Insta360等公司10个岗位
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
百度提前批一面 7.24
9801
2
...
字节复活赛
6290
3
...
不懂来大厂实习究竟能学到啥?
3744
4
...
百度提前批一面:面试官居然让我手撕两数之和???最奇幻的一轮面试,结束还说.......
3110
5
...
字节生活服务(杭州)一二三面(等HR or 挂)
3076
6
...
入我滴滴!早十晚六 !
2906
7
...
滴滴提前批面经
2684
8
...
百度二面面筋
2634
9
...
终章
2584
10
...
字节实习第三天10点下班,哭了
2237
创作者周榜
更多
正在热议
更多
#
哪些公司开提前批了?
#
27700次浏览
268人参与
#
入职以后才知道的校招谎言
#
88631次浏览
580人参与
#
风评不好的公司,你会去吗?
#
63319次浏览
450人参与
#
华子oc时间线
#
1244533次浏览
6485人参与
#
哪些公司校招卡第一学历
#
70122次浏览
280人参与
#
校招第一份工作你干了多久?
#
95288次浏览
423人参与
#
实习如何「偷」产出?
#
52704次浏览
1354人参与
#
除了主业以外,你还有哪些其他收入?
#
12535次浏览
202人参与
#
不卡学历的大厂有哪些?
#
30429次浏览
232人参与
#
机械人,你的第一份感谢信是谁给的
#
30598次浏览
310人参与
#
校招阶段,学历VS技术哪个更重要?
#
18163次浏览
188人参与
#
职场新人体验
#
27071次浏览
250人参与
#
研究所笔面经互助
#
78559次浏览
483人参与
#
工作丧失热情的瞬间
#
294122次浏览
2372人参与
#
腾讯音乐求职进展汇总
#
98254次浏览
570人参与
#
你的秋招第一场笔试是哪家
#
148219次浏览
1485人参与
#
社恐入职新公司如何融入团队
#
12042次浏览
63人参与
#
华为开奖那些事
#
4094394次浏览
24608人参与
#
校园里的破防时刻
#
11902次浏览
128人参与
#
Offer比较,你最看重什么?
#
191830次浏览
1308人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务