这是我正在寻找答案的问题：
数组 A[1...n] 包含从 0 到 n 的所有整数，除了一个。通过使用辅助数组 B[0...n] 记录哪些数字出现在 A 中，很容易在 O(n) 时间内确定丢失的整数。然而，在这个问题中，我们不能访问 A 中的整个整数一次操作。A 的元素以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，这需要恒定的时间。证明如果我们只使用这个操作，我们仍然可以在 O(n) 时间内确定丢失的整数。
我想到了这种方法：如果我没有上述获取限制，我会取所有数字并将它们一起进行 XOR。然后将结果与 1..n 中的所有数字进行异或运算。这将是我的答案。在这个问题中，类似地，我可以对数组中的所有元素在 log(n+1) 位的距离上重复异或不同数字的位，然后将它们与元素 1...n 异或，但复杂性出现在我看来是 O(nlogn)。
如何实现 O(n) 复杂度？谢谢
您可以使用基数排序的变体：
根据 MSb（最高有效位）对数字进行排序
您会得到两个大小为 n/2、n/2-1 的列表。您可以使用 n/2 个元素“删除”列表 - 缺少的数字不存在。
重复第二个 MSb，依此类推。
最后，您选择的“路径”（每个位的列表较小的位）将代表缺失的数字。
复杂性是O(n + n/2 + ... + 2 + 1)，因为n + n/2 + .. + 1 < 2n- 这是O(n)
为了简单起见，这个答案假设对于n=2^k一些整数k（这种放松可以稍后通过对 MSb 执行“特殊”句柄来放弃）。
你有 n 个整数，范围为 [0..n]。您可以检查每个数字的最高有效位并将这些数字分为 C（MSB 0）和 D（MSB 1）组。由于您知道范围是 [0..n]，因此您可以计算此范围内有多少 MSB 为 0 的数字，称为 S1，以及此范围内有多少 MSB 为 1 的数字，称为 S2。如果 C 的大小不等于 S1，那么你知道缺失的数字的 MSB 为 0。否则，你知道缺失的数字的 MSB 为 1。然后，你可以递归地解决这个问题。由于每个递归调用都需要线性时间，并且除了第一个递归调用之外的每个递归调用都可以是问题大小的一半，因此总运行时间是线性的。