-2

给定一个数组，任意两个后续元素之间的距离为 1（+1 或 -1）。我们得到了一个数字。我们如何以最小的复杂性检查数字是否在数组中。

4

6 回答 6

8

您可以进行某种二进制搜索。

如果我们要查找的元素在第一个和最后一个元素之间，我们知道该元素出现在数组中，我们可以停止。

如果不是，请检查数组中可能出现的最小值和最大值两者中。

更明确地说：

temp = abs(arr[left] - arr[right]) - (left - right)
minPossible = min(arr[left], arr[right]) - 2*temp
maxPossible = max(arr[left], arr[right]) + 2*temp

递归重复，将数组分成两半（或按照 Daniel 的建议进行拆分）。

为什么上面给出了可能的最小值/最大值：

可以这样想：你需要一些等于左右差的元素才能从一个到另一个。除此之外，对于您下/上的每一步，您都需要再次上/下。

仍然不幸的是不小于 O(n) 最坏的情况。

这就是为什么不能击败 O(n) 最坏情况的原因：

（类似于大卫的证明）。

示例输入 =[1,0,1,0,1,0,1,0]

假设我们正在寻找 2。

它显然不存在，但如果将其中一个 0 更改为 2 会怎样？我们需要检查每个零。一旦我们甚至跳过一个，那个可能就是 2。

因此我们必须检查至少 1/2 的元素，因此它仍然是 O(n/2) = O(n)。

于 2013-07-16T12:40:15.277 回答
5

您可以使用以下算法保存检查一些（可能是大多数）元素。

如果你的数字是 85 并且数组的第一个数字是 100，你可以跳过 (15-1) = 14 个数字（当然 15 是 100 和 85 之间的距离），因为它们最接近 85 的是 99、98 , 97, ..., 86。所以你只需检查第 15 个数字。如果该数字不是 85，请继续重复相同的算法。这使您可以跳过数组，该数组仍然是 O(N)，但时钟时间可能比仅逐个检查要快。

最坏的情况是：我正在寻找 85。

  • 第一个数字是 86。我不能跳过任何数字，因为 (1-1) = 0，下一个数字很可能是 85。
  • 我检查下一个数字。是 87。啊，现在我可以跳过一个数字，因为 (2-1) = 1; 我跳过的下一个数字可能是 88 或 86，但绝不是 85。
  • 我检查下一个数字，它是 86。
  • 一切都是一样的，因为数组实际上是 86、87、86、87、86、87……所以我最终检查了所有的 87，这几乎是数字的一半。

在阅读此答案之前，我认为这是最佳算法。

于 2013-07-16T12:32:45.967 回答
1

这个问题已经预料到单元探测复杂度 Ω(n)，因此不会发生次线性算法。考虑可能的输入

210101010...10
012101010...10
010121010...10
...
010101010...12

以相等的概率。找到 2。根据 Yao 引理，对于固定输入分布，最佳随机算法并不比最佳确定性算法好。在找到 2 之前，所有未被排除的输入看起来都相同。因此，每个正确的确定性算法都必须以某种顺序探测 0 位置，并探测预期的 n/4（或大约）位置，直到找到 2。

于 2013-07-16T12:48:38.923 回答
0

由于元素之间的差异为 1（+1 或 -1），因此min(array)和之间的任何数字max(array)都将在数组中。如果您缓存 min 和 max，那么第一个搜索O(N)是O(1).

如果数组的元素是分数而不是整数，那么还有一个额外的先决条件测试，fractionPart(min(array))-fractionPart(number)==0

于 2013-07-16T20:13:51.757 回答
0

当然复杂度不能小于O(N)。那就是说我会遍历整个数组。

无论何时

  • 读取值减去所需数字的绝对值大于 OR 后面的元素数
  • 读取值等于所需值

我会“打破”算法说“是”作为答案。

默认情况下，答案是“否”！:)

于 2013-07-16T12:19:51.297 回答
0

假设您v在数组中查找一个值。如果在给定位置i，该值a[i]是v-d我们要查找的值，至少d与i. 所以你可以跳过中间的单元格，因为 can 最多有 values v-d+1，v-d+2依此类推。所以这是一个草率的递归算法：

template <class ForwardIter, class T>
ForwardIter find_in_singlestep_range(ForwardIter first, ForwardIter last, T val) {
  if (first == last) return last;
  if (*first == val) return first;

  auto max_diff = last-first;
  auto diff = make_signed<T>{val} - make_signed<T>{*first};
  if (diff < 0) diff = -diff;
  if (diff > max_diff) return last;

  return find_in_singlestep_range(first+diff, last, val);
}

复杂性：您最多会得到 1/2*N +1 次比较，因为假设您从未遇到过该元素，最坏的情况可能是 diff 为 1,2,2,2,2，因此您跳过每个第二个元素。（如果 diff 为 2，则下一个 diff 只能是 2 或 4。）

如果您进行二分搜索，可能会有更好的复杂性：如果子数组的中间元素与子数组大小的差异val大于子数组大小的一半，则可以跳过子数组中的搜索。

于 2013-07-16T13:34:37.390 回答