首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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-25 15:35
已编辑
内蒙古大学 数据分析师
美团 金融服务平台 9.23 一面
9.25 更新 已回人才库2:00 - 3:00 【测试开发】1.自我介绍2.实习经历,实习中遇到的问题3.代码考察:一副扑克牌,四种花色,点数1-13 ,大小王共54张,大小王可以为任意花色和点数。任选两张牌点数之和为18的概率4.设计测试用例,用户名,密码,登录三个设计功能和非功能测试用例5.登录按钮的测试,怎么验证用户是合法的(回答的数据库,最后给讲解是cookie和session)6.反问(技术栈 Java,业务 )7.自己觉得有什么没有提到的优势或者回答的不好的地方补充MySQL 写sql语句 (查询 姓名 签到人员的次数)写成了 SUM having
点赞
评论
收藏
分享
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-27 20:08
已编辑
中国地质大学(武汉) 后端
【美团】金融服务平台-技术平台一面 (凉经)
整体时长:半小时自我介绍简单讲两三分钟。项目问答+八股考察在项目中怎么使用的 Caffeine 缓存Caffeine 比 Guava 好在哪介绍 Caffeine 的缓存刷新策略举例说明如何混合使用多种过期策略来满足复杂的缓存需求本地缓存和分布式缓存的差别什么情况下使用本地缓存,什么情况下使用分布式缓存项目中使用的什么消息中间件,什么时候需要使用消息中间件【感觉这里其实应该有一堆消息队列的问题】MySQL 的事务隔离级别什么是幻读,除了串行化,还能怎么解决幻读是只有插入和删除的时候会有幻读问题吗讲讲 MySQL 的锁Java 和 Scala 的区别讲讲 ConcurrentHashmap 当其...
你都收到了哪些公司的感谢信?
牛客创作赏金赛
点赞
评论
收藏
分享
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-29 17:10
中南大学 电力电子工程师
国家电网半年工作小记
首先,薪水还不错,收入相对丰厚。其次,稳定性是电网的一大优势。国企嘛,工作岗位相对固定。公司还会安排各种文体活动让我们参加,可以结识不同单位的人,社交圈子也在变化。至于加班嘛,这个就看具体单位和岗位了,我现在的单位加班不算频繁,整体还算轻松。不过,各地的待遇差异还是挺大的,和当地经济水平关系挺大的
国家电网工作强度 98人发布
点赞
评论
收藏
分享
点赞成功,聊一聊 >
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给正在秋招中枯燥的大家找个乐子听听吧,不被理解真的心寒
1.2W
2
...
26日常实习小红书面经
1.1W
3
...
牛客创作赏金赛:首发动态,100%拿现金!
1.1W
4
...
sagima的阎良出差日记
1.1W
5
...
秋招是时候收官了
9645
6
...
双非本科四年的总结
8308
7
...
请大家警惕“总包”骗局!
7831
8
...
秋招颗粒无收,我要何去何从
6916
9
...
收到offer了!!!!
6889
10
...
我的秋招结束了,五年前的我会想到这一切吗
6556
正在热议
#
25届秋招总结
#
243250次浏览
1984人参与
#
学历or实习经历,哪个更重要
#
40681次浏览
295人参与
#
北方华创开奖
#
22551次浏览
257人参与
#
地方国企笔面经互助
#
2484次浏览
6人参与
#
你最想要的公司福利是?
#
39333次浏览
112人参与
#
选完offer后,你后悔学本专业吗
#
9844次浏览
74人参与
#
面试题刺客退退退
#
136741次浏览
2087人参与
#
国企/银行/研究所公司爆料
#
89541次浏览
410人参与
#
应届生被毁约被毁意向了怎么办
#
26704次浏览
237人参与
#
机械应届生薪资要多少才合适?
#
12333次浏览
59人参与
#
查收我的offer竞争力报告
#
16360次浏览
223人参与
#
一觉醒来,我觉醒了超级打工人系统
#
2785次浏览
34人参与
#
校招入职后的感受
#
156706次浏览
1957人参与
#
没有实习经历,还有机会进大厂吗
#
804606次浏览
13808人参与
#
你觉得第一学历对求职有影响吗?
#
14823次浏览
121人参与
#
我的工作日记
#
21049次浏览
270人参与
#
不给转正的实习,你还去吗
#
1516139次浏览
16963人参与
#
寒假躺平还是提前实习
#
58189次浏览
433人参与
#
总结:哪家公司面试体验感最差
#
25506次浏览
128人参与
#
秋招OC许愿
#
226102次浏览
1864人参与
#
秋招被确诊为……
#
54270次浏览
302人参与
牛客网
牛客企业服务