我们可以用O(log n)来做Q1和Q2。

假设我们的存储芯片由n个试管阵列组成。试管中的数字x用x毫升化学液体表示。

假设我们的处理器是一束激光。当我们点燃激光时，它垂直穿过所有的管子。每次它通过化学液体，光度就降低1。在某毫升处通过光是O(1)的运算。

现在如果我们在试管的中间点上激光就会得到光度的输出

等于预先计算的值(当没有数字缺失时计算)，则缺失的数字大于n/2。 如果我们的输出更小，那么至少有一个小于n/2的数字缺失。我们也可以检查光度是否降低了1或2。如果它减少1，那么一个缺失数小于n/2，另一个大于n/2。如果它减2，那么两个数都小于n/2。

我们可以一次又一次地重复上述过程，缩小我们的问题域。在每一步中，我们将定义域缩小一半。最后我们可以得到结果。

值得一提的是并行算法(因为它们很有趣)，

sorting by some parallel algorithm, for example, parallel merge can be done in O(log^3 n) time. And then the missing number can be found by binary search in O(log n) time. Theoretically, if we have n processors then each process can check one of the inputs and set some flag that identifies the number(conveniently in an array). And in the next step each process can check each flag and finally output the number that is not flagged. The whole process will take O(1) time. It has additional O(n) space/memory requirement.

请注意，如上所述，上面提供的两个并行算法可能需要额外的空间。

我已经阅读了所有30个答案，并找到了最简单的一个，即使用100位数组是最好的。但正如问题所说，我们不能使用大小为N的数组，我将使用O(1)空间复杂度和k次迭代，即O(NK)时间复杂度来解决这个问题。

为了让解释更简单，假设给了我从1到15的数字，其中两个少了，即9和14，但我不知道。让包看起来像这样:

,1,2,12,4,7,5,10,11,13,15,3,6 [8].

我们知道每个数字在内部都是以位的形式表示的。 对于16之前的数字，我们只需要4位。对于10^9之前的数字，我们将需要32位。但我们先关注4位然后再推广它。

现在，假设我们有从1到15的所有数字，那么在内部，我们会有这样的数字(如果我们把它们排序):

0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

但是现在少了两个数。所以我们的表示法看起来是这样的(为了理解，可以是任何顺序):

(2MSD|2LSD)
00|01
00|10
00|11
-----
01|00
01|01
01|10
01|11
-----
10|00
missing=(10|01) 
10|10
10|11
-----
11|00
11|01
missing=(11|10)
11|11

现在让我们创建一个大小为2的位数组，其中包含具有对应的两位最高位的数字的计数。即

= [__,__,__,__] 
   00,01,10,11

从左到右扫描袋子，填充上面的数组，使比特数组的每个bin都包含数字的计数。结果如下:

= [ 3, 4, 3, 3] 
   00,01,10,11

如果所有的数字都出现了，它看起来会是这样的:

= [ 3, 4, 4, 4] 
   00,01,10,11

因此，我们知道有两个数字缺失了:一个数字的最高两位有效位数是10，另一个数字的最高两位有效位数是11。现在再次扫描列表，并为下两位有效数字填写一个大小为2的位数组。这一次，只考虑前两位有效数字为10的元素。我们将有位数组为:

= [ 1, 0, 1, 1] 
   00,01,10,11

如果MSD=10的所有数字都存在，那么所有箱子中都有1个，但现在我们看到少了一个。因此，我们有MSD=10和LSD=01缺失的数字，即1001，即9。

类似地，如果我们再次扫描，但只考虑MSD=11的元素，我们得到MSD=11和LSD=10缺失，即1110，即14。

= [ 1, 0, 1, 1] 
   00,01,10,11

因此，我们可以在等量的空间中找到缺失的数字。我们可以推广到100 1000或10^9或任何一组数字。

参考资料:http://users.ece.utexas.edu/~adnan/afi-samples-new.pdf中的问题1.6

您可能需要澄清O(k)的含义。

这里有一个任意k的简单解:对于你的数字集中的每一个v，将2^v相加。最后，循环i从1到n，如果和2^i按位和为零，则i缺失。(或者在数字上，如果和的底除以2^i是偶数。或者模2^(i+1) < 2^i

容易,对吧?O(N)时间，O(1)存储，支持任意k。

除了你在计算一个巨大的数字，在真正的计算机上，每个数字都需要O(N)个空间。事实上，这个解和位向量是一样的。

所以你可以很聪明地计算和，平方和和和立方体的和…直到v^k的和，然后用复杂的数学方法提取结果。但这些都是很大的数字，这就引出了一个问题:我们谈论的是哪种抽象的运作模式?O(1)空间中有多少是合适的，以及需要多长时间才能将所需大小的数字相加?

一个非常简单的Q2解决方案，我很惊讶没有人回答。用Q1的方法求两个缺失数字的和。我们用S表示它，那么缺失的数字中一个比S/2小另一个比S/2大(胡说)将从1到S/2的所有数字相加，并将其与公式的结果进行比较(类似于Q1中的方法)，以找到缺失数字之间的较低者。用S减去它，找出缺失的更大的数。

正如@j_random_hacker所指出的，这与在O(n)个时间和O(1)个空间中寻找重复项非常相似，我的答案在这里也适用。

假设“袋子”由一个大小为N - k的基于1的数组a[]表示，我们可以在O(N)个时间和O(k)个额外空间内求解Qk。

首先，我们将数组A[]扩展k个元素，使它现在的大小为n，这是O(k)个额外空间。然后我们运行以下伪代码算法:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化k个额外的条目，使其与数组中的第一个条目相同(这只是我们知道数组中已经存在的一个方便的值——在这一步之后，大小为N-k的初始数组中缺失的任何条目在扩展数组中仍然缺失)。

第二个循环排列扩展数组，如果元素x至少出现一次，那么其中一个元素将位于位置A[x]。

注意，尽管它有一个嵌套循环，但它仍然在O(N)时间内运行——只有当有一个i使a [i] != i时才会发生交换，并且每次交换设置至少一个元素使a [i] == i，而以前不是这样的。这意味着交换的总数(因此while循环体的执行总数)最多为N-1。

第三个循环打印数组i中没有被值i占用的索引——这意味着i一定是缺失的。

不确定，这是否是最有效的解决方案，但我会遍历所有条目，并使用bitset来记住，设置了哪些数字，然后测试0位。

我喜欢简单的解决方案，我甚至相信，它可能比计算和，或平方和等更快。