首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
々炫天空/yiw
2017-09-22 14:45
已编辑
中国科学技术大学 算法工程师
关注
已关注
取消关注
请教一道面试算法题~
平面上有N个点,求与其余N-1个点距离和(欧式距离,注意,不是平方和)最小的那点坐标。
如果是一维的话,就是排序后的中位数。
平面的话怎么处理呢,除了暴力o(n2)之外,有没有更优的办法
提示
全部评论
推荐
最新
楼层
已删除
羡慕会n^2的大佬,我只会O(n^3logn)
点赞
回复
分享
发布于 2017-09-22 14:44
端木森
The University of Queensland 科研人员
目测次梯度优化
点赞
回复
分享
发布于 2017-09-22 14:52
SuperBlack
保险职业学院 Java
二维难道不是两个中位数的组合吗?反正x y是互相不影响
点赞
回复
分享
发布于 2017-09-22 14:54
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
mnf86
浙江大学 安卓
先按x的大小排序,然后通过几何判断出和最大的点只能是第一个点或者最后一个点,比较一下这两个点的距离和,找出和最大的点?
点赞
回复
分享
发布于 2017-09-22 16:34
还没有回复哦~
相关推荐
09-27 20:08
已编辑
中国地质大学(武汉) 后端
【美团】金融服务平台-技术平台一面 (凉经)
整体时长:半小时自我介绍简单讲两三分钟。项目问答+八股考察在项目中怎么使用的 Caffeine 缓存Caffeine 比 Guava 好在哪介绍 Caffeine 的缓存刷新策略举例说明如何混合使用多种过期策略来满足复杂的缓存需求本地缓存和分布式缓存的差别什么情况下使用本地缓存,什么情况下使用分布式缓存项目中使用的什么消息中间件,什么时候需要使用消息中间件【感觉这里其实应该有一堆消息队列的问题】MySQL 的事务隔离级别什么是幻读,除了串行化,还能怎么解决幻读是只有插入和删除的时候会有幻读问题吗讲讲 MySQL 的锁Java 和 Scala 的区别讲讲 ConcurrentHashmap 当其...
你都收到了哪些公司的感谢信?
牛客创作赏金赛
点赞
评论
收藏
分享
09-25 21:15
南京航空航天大学 Java
美团面经
1. 0903 美团一面 - 1. springboot和springmvc的区别 2. mysql为啥不用b树,红黑树等 3. zset的实现;为什么用跳表;是不是一定用跳表 4. mvcc的具体实现 5. MQ保证消息可靠性 6. MQ的选型 7. 为啥要用MQ延迟双删保证mysql和redis一致性 8. hashmap的实现 9. 线程池的用法
美团一面1733人在聊
点赞
评论
收藏
分享
09-29 17:10
中南大学 电力电子工程师
国家电网半年工作小记
首先,薪水还不错,收入相对丰厚。其次,稳定性是电网的一大优势。国企嘛,工作岗位相对固定。公司还会安排各种文体活动让我们参加,可以结识不同单位的人,社交圈子也在变化。至于加班嘛,这个就看具体单位和岗位了,我现在的单位加班不算频繁,整体还算轻松。不过,各地的待遇差异还是挺大的,和当地经济水平关系挺大的
国家电网工作强度 98人发布
点赞
评论
收藏
分享
09-26 15:51
已编辑
中南大学 大数据开发工程师
美团秋招记录
9.14一面介绍项目项目中的ETL项目中的拉链表项目中的UDF项目中的Kmeans和DBSCAN八股说一下HDFS说一下进程和线程说一下数据倾斜说一下kafka说一下数仓的建模(雪花,星形,星座)说一下数仓分层的作用OLAP和OLTP的区别说一下数据库三范式手撕两道SQL手写冒泡排序(一面全部答出来了)9.18二面,二面感觉很考验对大数据的理解介绍项目项目中感觉做的最好的地方是哪些介绍一下中国软件杯的比赛你觉得你的项目和比赛在哪些地方体现出了大数据的思路讲讲你对大数据的理解讲讲你对数仓分层的理解讲讲你对数据仓库和数据库的区别的理解数仓和数据库都是SQL Boy, 你对两个SQL Boy的区别的理解有没有用过Doris和clickhouse(没有)说一下LSM Tree说一下Bit Map我看你项目里有lambda框架,讲一下lambda框架说一下Hive中的去重说一下模糊去重(这是真的不会。。。)说一下Kmeans和KNN的区别讲一下Java的集合框架手撕力扣原题,二叉树的层序遍历反问9.23 HR面介绍一下你自己为什么选择大数据你是保研的,你的成绩排名是多少为什么不选择考公或者读博你认为现在公司需要什么样的人才你在秋招的时候是怎么介绍自己的你自己有什么优势(疯狂推销自己,我学习能力强)你说你学习能力强,怎么体现出来的(幸亏我脑子转的快,答上来了)两道场景题1.你入职后,你的师傅负责带你学习,但是刚过了一周,你的师傅被紧急抽调了。这种情况下你如何学习技术。2.入职后,有人得到了晋升,而你没有。但是你感觉你自己的付出不少于他们。你会怎么做。反问9.26 oc #美团求职进展汇总#
美团求职进展汇总
点赞
评论
收藏
分享
09-26 16:29
武汉大学 Java
美团
有大佬知道美团三个志愿全部结束之后还会有机会被捞吗
找到工作就狠狠玩CSGO:
有机会的,我已经三战美团一面了😂
点赞
评论
收藏
分享
点赞成功,聊一聊 >
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
26日常实习小红书面经
1.7W
2
...
给正在秋招中枯燥的大家找个乐子听听吧,不被理解真的心寒
1.4W
3
...
sagima的阎良出差日记
1.2W
4
...
双非本科四年的总结
1.1W
5
...
秋招颗粒无收,我要何去何从
1.0W
6
...
双非学院本,转正云智!
9120
7
...
秋招是时候收官了
8698
8
...
收到offer了!!!!
7416
9
...
请大家警惕“总包”骗局!
7359
10
...
秋招之路:零基础游戏引擎/图形方向求职总结
6017
正在热议
#
25届秋招总结
#
248505次浏览
2018人参与
#
学历or实习经历,哪个更重要
#
41136次浏览
300人参与
#
北方华创开奖
#
22851次浏览
259人参与
#
地方国企笔面经互助
#
2559次浏览
6人参与
#
你最想要的公司福利是?
#
40099次浏览
126人参与
#
选完offer后,你后悔学本专业吗
#
10579次浏览
76人参与
#
面试题刺客退退退
#
137211次浏览
2092人参与
#
国企/银行/研究所公司爆料
#
89755次浏览
412人参与
#
应届生被毁约被毁意向了怎么办
#
27181次浏览
238人参与
#
一觉醒来,我觉醒了超级打工人系统
#
2916次浏览
35人参与
#
机械应届生薪资要多少才合适?
#
12398次浏览
60人参与
#
查收我的offer竞争力报告
#
16847次浏览
228人参与
#
校招入职后的感受
#
156973次浏览
1961人参与
#
你觉得第一学历对求职有影响吗?
#
14897次浏览
121人参与
#
没有实习经历,还有机会进大厂吗
#
805183次浏览
13814人参与
#
我的工作日记
#
21219次浏览
270人参与
#
不给转正的实习,你还去吗
#
1517140次浏览
16970人参与
#
寒假躺平还是提前实习
#
58463次浏览
438人参与
#
总结:哪家公司面试体验感最差
#
25775次浏览
129人参与
#
秋招OC许愿
#
226722次浏览
1872人参与
#
如何写一份好简历
#
602304次浏览
8444人参与
牛客网
牛客企业服务