我向硬件提出了这个问题，但我不知道该怎么做:
数组 A[1...n] 包含从 0 到 n 的所有整数(除了 1 之外)。数组未排序。
在这个问题中，我们无法通过单个操作访问 A 中的整个整数。
A 的元素以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，这需要常数时间。
我必须在 O(n) 时间内找到丢失的整数。
正常情况下完成该操作所需的时间为 O(NlgN) (在 N 数组上运行，并获取 N - lgn 位函数的所有位)。
如何在不读取所有位的情况下做到这一点？
最佳答案
现在我们假设对于某些 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 分区。
关于algorithm - 将运行时间减少到 O(n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10447569/