Facebook 一面

第一题必须o(n) 吧 一个loop 就行了 还能优化？

个人愚见：第一题如果数组是随机的，只能是Ｏ(n)的方法。如果你跳过任何一个，都无法得出valid的结论，所以必须检查所有的元素。

同意楼上，感觉必须O(n)，楼主可以细讲讲怎么logn嘛？

面无表情 发表于 2016-2-18 04:00
同意楼上，感觉必须O(n)，楼主可以细讲讲怎么logn嘛？

额。。楼主只做了O(n), 这道题并没有 follow up~

如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)

什么结果什么结果

zxl9171 发表于 2016-2-19 02:07
如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)

相邻只能+-1的话，似乎也不能确保能Log N解决。请问下你的思路是？

zxl9171 发表于 2016-2-19 02:07
如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)

如果是+-1的话O（1）就可以了

怎么我以为第一题的意思是，符合要求的数组是类似于1，2，3，4 或者5，3，2，0这种。。。所以楼主这道题是说一个数组，一段递增一段递减也可以吗？还是别的我没理解？。。。