Google 2015-10-2 MTV 另求教

stellari 发表于 2015-10-3 16:44
找1/2majority的话，其实没必要移整个范围。可以先取得a[(size-1)/2] == midval的值，如果1/2majority存 ...

受四楼启发...
我觉得Question6可以这么来做:
假设数组的size为len，a = len / 8;分别检测以下9个坐标的值
nums[0], nums[a],nums[a*2],nums[a*3],nums[a*4],nums[a*5],nums[a*6],nums[a*7], nums[len]
因为数组是sorted的，如果存在元素出现的次数more than 1/4 times，那么必然以上有两个相邻的元素share同一个值，找出这些值作为candidates。然后分别使用binary search找出这些值的左边界和右边届。如果如果左右边界之差满足 > len/4. 那么就找到了这个元素。

我ONSITE也是五轮

airwindow 发表于 2015-10-7 08:35
受四楼启发...
我觉得Question6可以这么来做:
假设数组的size为len，a = len / 8;分别检测以下9个坐标 ...

确实是这么做

第三题很多人没看懂，解释一下：index为偶数的是值，会出现在结果中，就是你call next()时有可能输出，index为奇数的是它前面那个数出现的次数。不知道说清楚了没。。

还是不太 清楚啊,能否再举个例子下?

多谢楼主分享，不过第二题 不是特别明白， 需要考虑时间么，如果只看 A->B 的话，如果有回路出现怎么办呢

我觉得中国人就是在放水

白露为霜 发表于 2015-10-11 16:06
多谢楼主分享，不过第二题 不是特别明白， 需要考虑时间么，如果只看 A->B 的话，如果有回路出现怎么办呢

他说假设没回路

qiuxuxing007 发表于 2015-10-9 11:13
还是不太 清楚啊,能否再举个例子下?

如果输入是 [3,2, 5, 1]， 第一次call next()， you get 3, 第二次call next(), you get 3. 第三个call next(), you get 5. So the output should be [3,3,5]. input中只有index为偶数的才可以出现在Output中。input中index的奇数代表它前面那个数能输出几次。

请问楼主过了吗？