在数组中找到一个元素，其中每个元素比其前面的元素多一个或少一个

Question

给定一个数组，每个元素比其前面的元素.find多一个或少一个，其中一个元素(比O(n)方法好)

我对此有一个解决办法，但我无法正式判断这是否是正确的解决办法：

让我们假设我们必须找到n。

• 从给定的索引中，找出到n；d= given的距离。
• 所需的元素至少是分开的d元素和跳转的d元素
• 重复以上，直到d =0

Answer 1

是的，你的方法会奏效的。

如果您只能在每个后续索引上增加/减少一个值，那么在一个索引上的值不可能比d更接近于一个d与当前值之间的距离。因此，您不可能跳过目标值。而且，除非找到这个值，否则距离总是大于0，所以你会一直向右移动。因此，如果值存在，您将找到它。

不，在最坏的情况下，你不能比O(n)做得更好。

考虑一个数组1,2,1,2,1,2,1,2,1,2,1,2，您正在寻找0。任何一个2都可以更改为0，而不必更改任何其他值，因此我们必须查看所有的2，还有n/2 = O(n) 2。

Answer 2

预科能帮上忙。在O(n)时间复杂度中求数组的最小和最大元素。如果要查询的元素介于数组的最小和最大之间，则该元素存在于数组中，否则该元素在该array.So中不存在--任何查询都需要O(1)时间。如果该数组被多次查询，则摊还时间复杂度将小于O(n)。