狗家 Google summer 2019 intern 10.1 OA

qibaoshen3

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

给小伙伴们报个平安，好像真的如其他人分析的一样，9月份发的OA都是一样的。

1. 学生按身高站队，要求新来的学生必须站

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

米啊各位，虽然不是什么救命帖子，但是最近用米真的很多！祝各位好运！

qibaoshen3

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

qibaoshen3 · 2018-10-24 04:40:45

simonwux1 发表于 2018-10-12 16:02
求问houseandstore是分别排序后然后找比当前house要大的store进行比较吗？查找过程O（m+n）？

只用排序一下store，然后用每一个house元素去binary search一下sorted store就好了。

qibaoshen3 · 2018-10-24 04:44:21

Yifdaddy 发表于 2018-10-10 12:15
求第二题的详细思路。。。。谢谢

不好意思回复晚了。先把store的位置sort一下，然后用house里面的每个元素binary search 一下sorted store，找到最近的store就可以。

test_temp

楼主能具体说一下解法吗，跪谢

yubowang1996

第二题如果讲两个都sort 然后O(m + n) 的遍历算更优化一点吗虽然那样的话runtime还是O(nlogn) 因为sort的问题而且需要O(n)的空间

Yifdaddy · 2018-10-10 12:15:42

求第二题的详细思路。。。。谢谢

lic120 · 2018-10-11 13:09:36

“反之就去找list里面第一个比新身高大的数值并把它替代” 请问这里需不需要用到binary search?

simonwux1 · 2018-10-12 16:02:24

求问houseandstore是分别排序后然后找比当前house要大的store进行比较吗？查找过程O（m+n）？

qibaoshen3 · 2018-10-24 04:38:21

lic120 发表于 2018-10-11 13:09
“反之就去找list里面第一个比新身高大的数值并把它替代” 请问这里需不需要用到binary search?

我觉得可以用，但是题目不要求效率，所以还是看你啦

qibaoshen3 · 2018-10-24 04:42:32

yubowang1996 发表于 2018-10-9 12:09. Χ
第二题如果讲两个都sort 然后O(m + n) 的遍历算更优化一点吗虽然那样的话runtime还是O(nlogn) 因为sort的 ...

我觉得可以哦，不过题目不要求效率。good idea。