algorithm - 将运行时间减少到 O(n)

Question

我收到了 HW 的这个问题，但我不知道该怎么做:
数组 A[1...n] 包含从 0 到 n 除了 1 之外的所有整数。数组未排序。
在这个问题中，我们无法通过一次操作访问 A 中的整个整数。
A 的元素以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，这需要常数时间。

我必须在 O(n) 时间内找到丢失的整数。

正常情况下需要的时间是O(NlgN)(在 N 数组上运行，并获取所有作为 N - lgn 位函数的位)。

如何在不读取所有位的情况下做到这一点？

Answer 1

现在让我们假设对于某个 k，n 是 2^k - 1。

我们再来看一个 k = 3 的例子。

000
001
010
011
100
101
110
111

您会注意到，当有一个完整的集合时，如上图所示，每一列(每个数字的位置)都有相同数量的 1 和 0。当然，为方便起见，我们将其显示为已排序，但实际上，我并没有声明它是排序的。

我们来看看下面的列表

000
001
010
011
100
110
111

我们查看所有元素的第一位 ( O(n) ) 并找出哪个计数小于另一个。

我们看到，对于第一位，有一个数字的最高有效位缺失了 1。这意味着我们知道我们的数字的最高有效位是 1。

基本上，我们分成两组，一组最高有效位为 1，另一组最高有效位为 0。较小的一组显示缺失数字的位。

我们在较小的分区上做同样的事情。

因为它是 O(n) + O(n/2) + O (n/4) ... 它基本上是 O (2n) 也就是 O (n)。

编辑

一般情况引用the following document, bottom of page 1 .

基本上，它涉及利用这样一个事实，即当 n 不是 2 的幂时，您可以考虑这样一个事实，即给定 n，您确切地知道有多少应该属于 bit=1 分区和 bit=如果这是一个完整的集合，则为 0 个分区。