首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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-24 11:56
上海交通大学 嵌入式软件开发
实习三偷定律,如何偷到重点
先上结论: 实习期间一定要多问,多学,多偷! 当然不是偷东西的偷,主要是偷产出,来一招 四两拨千斤, A姐做的=我的,B哥做的也=我的,只要我不说这些产出都是我的。实习最重要的就是整合,整合你在实习期间的所有的技术/知识,转化成可以加分的东西 比如项目/数据/经验 等等 一定要在你简历上展现。转化率低的话,要么是你不会整合,要么就是太打杂了,一句话跑路。如何增加自己的产出:我总结了三偷定律:偷学,偷聊,偷需求1.偷学你所在的组负责的项目一定是为了解决一个具体的业务问题,对于大公司来说,你负责的项目可能是一整个大的架构中的其中一环。因此多翻一翻关于这个项目的立项书以及各种相关资料。领导让你做的不...
点赞
评论
收藏
分享
07-23 11:56
魔门塔(苏州)科技有限公司_感知算法工程师(准入职员工)
momenta内推
momenta日常实习面经-嵌入式软件开发,摘自优秀牛友👋一面:1.freertos优先级有几种模式 2.freertos的任务调度 3.freertos的任务优先级设置的值越大,优先级是越高还是越低 4.Linux移植根文件系统用什么做的 5.编译流程 6.MQTT的了解 7.长连接和短连接 8.cmake和makefile 9.git 10....
点赞
评论
收藏
分享
06-09 23:07
已编辑
湖北工程学院新技术学院 运营
求捞一手
有没有哥哥姐姐捞一手啊,我一周内想去北京发展。°(°¯᷄◠¯᷅°)°。
我在牛客求捞
点赞
评论
收藏
分享
07-22 18:08
中山大学 机械结构工程师
速腾聚创2面结束直接终止流程
面了半天面试官感觉我的项目不对口,说的不对,但是我按照他的意思都是引导的,他觉得我没有自己的思考,项目不对口,双9也没用,今年好像只要硕士我了解的速腾:100%转正,双休,995,除基本薪资外没什么别的补贴,但我终归是信息局限,
速腾聚创二面26人在聊
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
百度提前批一面 7.24
1.3W
2
...
字节复活赛
9030
3
...
不懂来大厂实习究竟能学到啥?
4139
4
...
字节生活服务(杭州)一二三面(等HR or 挂)
4104
5
...
滴滴提前批面经
3527
6
...
百度提前批一面:面试官居然让我手撕两数之和???最奇幻的一轮面试,结束还说.......
3443
7
...
入我滴滴!早十晚六 !
3179
8
...
终章
2806
9
...
字节实习第三天10点下班,哭了
2561
10
...
团子呆了一个多月,想走的欲望达到的了顶峰
2514
创作者周榜
更多
正在热议
更多
#
哪些公司开提前批了?
#
27942次浏览
268人参与
#
入职以后才知道的校招谎言
#
88698次浏览
583人参与
#
风评不好的公司,你会去吗?
#
63603次浏览
450人参与
#
华子oc时间线
#
1244628次浏览
6487人参与
#
哪些公司校招卡第一学历
#
70435次浏览
280人参与
#
校招第一份工作你干了多久?
#
95316次浏览
423人参与
#
实习如何「偷」产出?
#
52996次浏览
1355人参与
#
除了主业以外,你还有哪些其他收入?
#
12637次浏览
202人参与
#
不卡学历的大厂有哪些?
#
30701次浏览
232人参与
#
机械人,你的第一份感谢信是谁给的
#
30615次浏览
310人参与
#
校招阶段,学历VS技术哪个更重要?
#
18267次浏览
188人参与
#
职场新人体验
#
27312次浏览
251人参与
#
研究所笔面经互助
#
78584次浏览
483人参与
#
工作丧失热情的瞬间
#
294155次浏览
2372人参与
#
腾讯音乐求职进展汇总
#
98286次浏览
571人参与
#
你的秋招第一场笔试是哪家
#
148296次浏览
1485人参与
#
社恐入职新公司如何融入团队
#
12071次浏览
63人参与
#
华为开奖那些事
#
4094737次浏览
24608人参与
#
校园里的破防时刻
#
12038次浏览
128人参与
#
Offer比较,你最看重什么?
#
191893次浏览
1308人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务