algorithm - 报告整数数组中的所有缺失数字(以二进制表示)

Question

我最近有一个 friend 告诉我，在一次工作面试中，他被问到以下问题，这个问题似乎很受欢迎:

给你一个列表 L[1...n]它包含从 0 到 n 的所有元素，除了一个。此列表的元素以二进制表示 and are not given in any particular order ，我们可以用来访问它们的唯一操作是在常数时间内获取 L[i] 的第 j 位。 如何找到 O(n) 中缺失的号码？

他能够回答这个问题(我相信这个问题有多种解决方案，但没有一个太复杂)。例如，下面的伪代码解决了上面的问题:

Say all numbers are represented by k bits and set j as the least significant bit (initially the rightmost).<br/> 1. Starting from j, separate all the numbers in L into two sets (S1 containing all numbers that have 1 as its jth bit, and S2 containing all numbers that have 0 in that position).<br/> 2. The smaller of the two sets contains the missing number, recurse on this subset and set j = j-1

在每次迭代中，我们将集合的大小减半。所以最初我们有 O(n)，然后是 O(n/2)，O(n/4) ... = O(n)

但是后续问题是:“如果我们现在的列表 L 中缺少 k 个数字，我们希望报告所有 k 个数字，同时仍然保留O(n)复杂度和初始问题的局限性？怎么办？

有什么建议吗？

Answer 1

bool J[1..n + 1]={false,false...}
int temp;

for(i = 1; i <= n; i++)
{
    temp=bitwisecopy of L[i];
    J[temp + 1]=true
}

for(i = 1; i <= n+1; i++)
{
    if(J[i]==false)
       print i + 1;
}

大声笑，这就是它的主旨......我认为索引可能搞砸了。

我对问题的理解是否正确？我不是很清楚唯一的操作是访问 L[i] 的第 j 位的确切含义。