arrays - 在一组 {0......2^k -1} 范围内找到缺失的数字

Question

给定一个包含数字 {0......2^k -1} 除了一个数字的数组， 找到一个好的算法来找到丢失的数字。

请注意，您只能使用:

• 对于 A[i] 返回位 j 的值。

• 用 A[j] 交换 A[i]。

我的答案:使用分而治之，检查所有数字的位数 K，如果 K 位(现在我们在 LSB 上)是 0 然后将数字移动到 left side，如果K位是1，则将数字移到右侧。 第一次迭代后，我们有两组，其中一组比另一组大，所以我们继续用较小的组做同样的事情，我认为我需要检查 K-1 位时间。

但出于某种原因，我尝试使用 0.....7 中的 8 个数字，并删除了 4(假设我想找出4 是缺失的数字)，但是算法并没有那么好。那么我的错误在哪里？

Answer 1

我假设您可以使用 get bit j 构建 xor bit 函数。

答案将是(所有数字的异或)

证明:a xor (2^k-1-a) = 2^k-1(a 和 (2^k-1-a) 将有前 k 个位置的不同位)。
然后 0 xor 1 xor ... xor 2^k-1 = (0 xor 2^k-1) xor (1 xor 2^k-2).... (2^(k-1) 对) = 0。
如果缺少数字 n，则结果将为 n，因为 0 xor 1 xor 2....xor n-1 xor n+1 xor ... = 0 xor 1 xor 2....xor n-1 xor n+1 xor ... xor n xor n = 0 xor n = n

编辑:如果 k = 1，这将不起作用。