算法分析 - 在排序数组中查找缺失的整数，时间复杂度优于O(n)

Question

算法分析 - 在排序数组中查找缺失的整数，时间复杂度优于O(n)

arraysalgorithmsortingasymptotic-complexity

8

我正在第一次学习算法分析课程，并想知道是否有人可以协助下面的例子。我相信我已经用O(n)复杂度解决了它，但是我想知道是否有更好的 O(logn) 解法？

让 A = A[1] <= ... <= A[n+1] 成为一个排序好的数组，包含 n 个不同的整数，每个整数在 [1...n+1] 的范围内。换句话说，{1,...,n+1} 中恰有一个整数不在 A 中。请描述一种有效的算法来查找缺失的整数。分析您的算法的最坏情况复杂度（对数组 A 的访问次数）。

我的解决方案相对简单，我认为结果在最坏情况下是 N 的复杂度。也许我对这个例子过于深思熟虑了，但是有没有更好的解决方案呢？

我的解决方案：

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

这个方法的逻辑是，由于数组已经排序，第一个元素必须是1，第二个必须是2，以此类推，直到数组中的元素比它应该的元素大，表示漏了一个元素，返回应该的元素即为缺失的元素。

这个逻辑正确吗？有更好的方法吗？

感谢阅读和提前的帮助。

- Busturdust

是的，有更好的解决方案。提示：你真的需要查看数组中的每个元素吗？ - aquinas

请问您能否整理一下问题陈述？(1) 如果A是不同的，那就意味着它们不相等；那么为什么不直接说“A[1] < A[2] < …”呢？(2) 如果{A[1]，A[2]，…，A[n+1]} ⊆ {1，2，…，n+1}，那么∀i，A[i]=i，因此没有缺失的整数。您的文本中说“n个不同的整数”，所以它不能是A[1]，A[2]，…，A[n+1]。(3) 您的问题陈述说A从A[1]开始，但您的解决方案从A[0]开始（在评论中，您说数组索引从[0]开始）。 - Scott - Слава Україні

3个回答

8

您可以使用二分查找来找到第一个索引i，使得A[i] > i。如果缺失的整数为k，则对于i < k，A[i] = i，而对于i >= k，A[i] = i + 1。

- Paul Hankin

3

有时候解决问题的诀窍在于用不同的方式思考问题。

从本质上讲，您只是使用一个布尔值数组；索引n处的条目是a[n] > n的真值。

此外，此数组以零个或多个连续的false开头，其余的条目都是true。

现在，您的问题是找到布尔值数组中第一个实例true的索引（已排序）。

- user1084944

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

这个逻辑是正确的，但是它不够快以击败 O(n)，因为你需要检查每个元素。

你可以通过观察到如果 A[i]==i，那么所有在 j < i 的元素都在它们应该在的位置上。这个观察足以构建一个分治方法，在 O(log₂n) 的时间内运行：

检查中间的元素
如果它在错误的位置，就向左走
否则，向右走

更正式地说，你正在寻找一个地方，使得 A[i]==i 且 A[i+1]==i+2。你从数组的两端开始。每次在区间中间进行探测会将剩余区间缩小一倍。最终你会留下只有两个元素的区间。左边的元素是最后一个 "正确" 的元素，而右边的元素是缺失数字后的第一个元素。