给定一个数组，每个元素都比它的前一个元素多一个或少一个。在其中找到一个元素。（优于 O(n) 方法）
我对此有一个解决方案，但我无法正式判断它是否是正确的解决方案：
假设我们必须找到 n。
- 从给定的索引，找到到 n 的距离；d = |a[0] - n|
- 所需的元素将至少是
d分开的元素和跳跃d元素 - 重复上述直到
d= 0
问问题
893 次
2 回答
8
是的，你的方法会奏效。
如果您只能在每个后续索引处增加/减少 1，则索引处的值d不可能比d与当前值的距离更近。因此，您无法跳过目标值。而且，除非找到该值，否则距离将始终大于 0，因此您将继续向右移动。因此，如果该值存在，您就会找到它。
不，你不能比O(n)最坏的情况做得更好。
考虑一个数组1,2,1,2,1,2,1,2,1,2,1,2，您正在寻找0. 任何2' 都可以更改为 a0而无需更改任何其他值，因此我们必须查看所有2' 并且有n/2= O(n) 2。
于 2013-11-11T08:44:00.363 回答
0
预处理可以在这里提供帮助。以 O(n) 时间复杂度查找数组的最小和最大元素。如果要查询的元素介于数组的最小值和最大值之间，则该元素存在于数组中，否则该元素不存在于该数组中。因此任何查询都需要 O(1) 时间。如果多次查询该数组，则摊销时间复杂度将小于 O(n)。
于 2016-05-08T19:09:28.027 回答