二进制字符串的线性算法

Question

我正在经历一些旧的中期学习.(没有给出解决方案)

我遇到过这个我坚持的问题

5. 对于某个正整数l,设n = 2 ^l - 1.假设有人声称拥有一个不同的ℓ比特串的数组A [1 .. n]; 因此,A中没有出现一个ℓ比特的字符串.进一步假设我们可以访问A的唯一方法是调用函数FetchBit(i,j),它返回字符串A [i]的^第 j 位O(1)时间.
   描述一种算法,仅使用对FetchBit的O(n)调用来查找A中缺少的字符串.

我唯一能想到的是遍历每个字符串,将其转换为基数10,对它们进行排序,然后查看缺少哪个值.但那肯定不是O(n)

证明它不是功课... http://web.engr.illinois.edu/~jeffe/teaching/algorithms/hwex/f12/midterm1.pdf

Answer 1

你可以在2n次操作中完成.

首先,查看每个数字的第一位.显然,你会得到^2ℓ-1零和^2ℓ-1 -1,反之亦然(因为只有一个数字丢失).如果有2 ^l-1 -1,那么你知道缺失数字的第一位是1,否则它是0.

现在你知道丢失数字的第一位了.让我们看看所有具有相同第一位的数字(其中有2 ^l-1 -1)并用它们的第二位重复相同的程序.这样您就可以确定缺失数字的第二位,依此类推.

FetchBit总数呼叫将是2 ^ℓ -1 + 2 ^ℓ-1 -1 + ... + 2 ¹ -1 <= 2 ^{ℓ+ 1} <= 2N + 2 = O(n)中.