Mic*_*ael 7 language-agnostic arrays algorithm
这是一个面试问题.给定排序的整数数组和数字z,找到数组中的所有对(x,y),使得x + y <z.它可以比O(n ^ 2)更好吗？
PS我知道我们可以在O(N)中找到所有对(x,y | x + y == z).
tem*_*def 9
您不一定能在O(n)时间内找到所有这些对,因为可能有O(n 2)对具有此属性的值.通常,算法运行时间不能少于它生成的值的数量.
希望这可以帮助!
CB *_*ley 5
在生成中,不,它不能.考虑的情况下x + y < z为所有x,y在数组中.您必须触摸(例如显示)n(n - 1)/2集合中的所有可能对.这基本上是O(n ^ 2).
x + y < z
x
y
n(n - 1)/2
归档时间：
13 年，9 月 前
查看次数：
1390 次
最近记录：
8 年，2 月 前