Google电面

上来直接给题，实在太直接了。。。
float []a = {  ...

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

对面在忙别的，45分钟到了就挂了。

请问楼主，array 是sorted 的么， 能否举个列子w区间是怎么定义的呢，多谢

我的一个想法是先Sort，然后对每一个元素作为中点，算出它能覆盖到的范围，然后往两边做Binary Search，这样的话时间复杂度是O(n log n)。不知道有没有更好的。

补充内容 (2014-12-18 07:42):
刚刚跟同学讨论了一下，sort之后可以不用两边二分查，维护一个长度为W的动态窗口就好，这样搜一遍就可以，除去sort之外，O(n)就可以了

lklk1986fa 发表于 2014-12-18 05:36
请问楼主，array 是sorted 的么， 能否举个列子w区间是怎么定义的呢，多谢

array是unsorted，w的定义的话比如float w = 0.28, 可以随便取区间但是长度都是0.28，需要求出能够包含在此区间长度的最多的number。

GabrielYeah 发表于 2014-12-18 07:17
我的一个想法是先Sort，然后对每一个元素作为中点，算出它能覆盖到的范围，然后往两边做Binary Search，这 ...

先sort没问题。但是不能把元素作为中点。我的想法是遍历，每次把元素作为左边界，设为i，求出i能够到达的最远的number，设为j，update最大值为j-i+1。但是不知道怎么把复杂度弄成O(n)。
你说的维护窗口的具体是怎么实现的？求指导。

mayingjie116 发表于 2014-12-18 09:58
先sort没问题。但是不能把元素作为中点。我的想法是遍历，每次把元素作为左边界，设为i，求出i能够到达的 ...

大概双指针可以维护这个窗口。

两个指针初始都从第一个元素出发，移动右指针直到超出窗口大小，用右指针的index减去左指针的index，得到一个该窗口内元素个数，更新maximum; 之后移动左指针直到再次满足窗口大小，继续移动右指针到超出窗口大小，更新maximum.

lqs4188980 发表于 2014-12-18 10:34
大概双指针可以维护这个窗口。

两个指针初始都从第一个元素出发，移动右指针直到超出窗口大小，用右指 ...

我演算了一下，这是个很棒的思路。
在i移动时，可以保证i-j窗口内包含的数字个数不超过maximum。

mayingjie116 发表于 2014-12-18 09:58
先sort没问题。但是不能把元素作为中点。我的想法是遍历，每次把元素作为左边界，设为i，求出i能够到达的 ...

嗯，前面没考虑好，中点是不行的，动态窗口就是楼上说的方法。

GabrielYeah 发表于 2014-12-18 14:48
嗯，前面没考虑好，中点是不行的，动态窗口就是楼上说的方法。

很棒的思路！