我有个问题要问硬件，我不知道怎么做：
数组a[1…n]包含从0到n的所有整数，只有一个除外。数组未排序。
在这个问题中，我们不能用一个操作访问A中的整个整数。
a的元素用二进制表示，我们可以用来访问它们的唯一操作是“获取a[i]的第j位”，这需要恒定的时间。
我必须在O（N）时间内找到丢失的整数。
现在做这件事所需的时间是O（NlgN）
（在N数组上运行，并获取N-lgn位函数的所有位）。
我怎么能不把所有的信息都读出来呢？
最佳答案
现在假设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，另一组最有效位是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/