ForUsAll为了我们全部8月OA新题

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

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

BigShaun 发表于 2018-9-18 08:09
前面分析的很好！但是后面对任意R找到一个L是N^2了。

题目提示的复杂度比较容易想到用binary search。 ...

这里R和L的区间都是单调的，用2 pointers就可以做到O(N)

hitr2997925 发表于 2018-8-5 05:34
但是"对於一个给定的r去找最大的l"要O(N), 而又有O(N)个r可以给定, 所以整个search有可能要O(N^2)?

"对於一个给定的r去找最大的l"是平摊O(1)的