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

Question

给定一个{0......2^k -1}除了一个数字之外的数字的数组,找到一个找到缺失数字的好算法.

请注意,您只能使用:

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

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

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

但是出于某种原因,我尝试过使用8个数字,从中0.....7删除4(并且说我想要找出4丢失的数字),但算法并没有那么好用.那我的错误在哪里？

Answer 1

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

答案是(所有数字的xor)

证明: 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) pairs) = 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,这将不起作用.

Answer 2

罗恩，

你的解决方案是正确的。这个问题有点像快速排序，不是吗？

你对第 K 位（左边全是 0，右边全是 1）所做的就是所谓的分区 - 你需要成对地找到放错位置的元素并交换它们。这是霍尔选择和快速排序中使用的过程，具有特殊的元素分类 - 无需使用枢轴元素。

您忘记在问题陈述中说明数组中有多少个元素（2^k-2 或更多），即是否允许重复。

如果不允许重复，那么每个分区确实会因为一个元素而变得不平衡。使用的算法是霍尔选择的一个实例（仅划分最小的一半）。在每个分区阶段，要考虑的元素数量减半，因此运行时间为 O(N)。这是最佳的，因为在找到解决方案之前需要知道每个元素。

[如果允许重复，请使用修改后的快速排序（递归地划分两半），直到到达空的一半。那么运行时间可能是 O(N Lg(N))，但这需要检查。]

你说算法在你的测试用例上失败了：你可能错误地实现了一些细节。

一个例子：

从 5132670 开始（这是范围 {0..7}）

按位权重 = 4 进行分区后，您将得到 0132|675

其中最短的一半是 675（这是范围 {4..7}）

按位权重 = 2 进行分区后，得到 5|67

其中最短的一半是 5（这是范围 {4..5}）

按位权重 = 1 进行分区后，得到 |5

其中最短的一半是空的（这是范围 {4}）。完毕。