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

Question

给定一个数组，每个元素比它前面的元素多一或少一。在其中找到一个元素。(比 O(n) 方法更好)

我有一个解决方案，但我无法正式判断它是否是正确的解决方案:

假设我们必须找到 n。

• 根据给定的索引，找到到n的距离； d = |a[0] - n|
• 所需的元素将至少相隔 d 个元素并跳转 d 个元素
• 重复上述直到d = 0

Answer 1

是的，您的方法会奏效。

如果您只能在每个后续索引处增加/减少 1，则距离 d 更近的索引处的值不可能与当前索引的距离为 d值(value)。所以你无法跳过目标值。而且，除非找到该值，否则距离将始终大于 0，因此您将继续向右移动。因此，如果该值存在，您就会找到它。

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

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