我会用另一种方法来回答这个问题，询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求，显而易见的基于集的解决方案可能是正确的，而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

这当然不是批处理预先生成的数字袋的最快方法，因为整个过程运行O((log 1 + log 2 +…)+ log n) + (log n + log n-1 +…+ log k))。但它确实适用于任何k值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

你可以通过阅读Muthukrishnan的几页-数据流算法:谜题1:寻找缺失的数字来找到它。它准确地显示了您正在寻找的泛化。也许这就是面试官读到的内容，也是他提出这些问题的原因。

还请参阅sdcvvc的直接相关答案，其中还包括伪代码(万岁!没有必要阅读那些棘手的数学公式:)(谢谢，干得好!)

等一下。正如问题所述，袋子里有100个数字。无论k有多大，问题都可以在常数时间内解决，因为您可以使用一个集合，并在最多100k次循环迭代中从集合中删除数字。100是常数。剩下的数就是你的答案。

如果我们将解推广到从1到N的数字，除了N不是常数外，没有什么变化，所以我们在O(N - k) = O(N)时间内。例如，如果我们使用位集，我们在O(N)时间内将位设置为1，遍历这些数字，将位设置为0 (O(N-k) = O(N))，然后我们就得到了答案。

It seems to me that the interviewer was asking you how to print out the contents of the final set in O(k) time rather than O(N) time. Clearly, with a bit set, you have to iterate through all N bits to determine whether you should print the number or not. However, if you change the way the set is implemented you can print out the numbers in k iterations. This is done by putting the numbers into an object to be stored in both a hash set and a doubly linked list. When you remove an object from the hash set, you also remove it from the list. The answers will be left in the list which is now of length k.

还有一种方法是使用残差图滤波。

假设数字1到4少了3。二进制表示如下:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

我可以创建一个像下面这样的流程图。

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

注意，流图包含x个节点，而x是比特数。最大边数是(2*x)-2。

因此，对于32位整数，它将占用O(32)空间或O(1)空间。

现在如果我从1,2,4开始移除每个数的容量那么我就剩下了一个残差图。

0 ----------> 1 ---------> 1

最后我将像下面这样运行一个循环，

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

现在的结果是结果中包含的数字也没有缺失(假阳性)。但是当有k个缺失元素时，k <=(结果的大小)<= n。

我将最后一次检查给定的列表，以标记缺少或没有的结果。

所以时间复杂度是O(n)

最后，可以通过选取节点00、01、11、10而不是0和1来减少误报的数量(以及所需的空间)。

下面是Dimitris Andreou链接的摘要。

记住i次幂的和，其中i=1 2 .. k。这就把问题简化为解方程组

A1 + A2 + ... + AK = B1

A12 + A22 + ... + AK2 = B2

...

a1k + a2k + ... + laas = bk

利用牛顿恒等式，知道bi就可以计算

c1 = a1 + a2 +ak

c2 = a1a2 + a1a3 +，+ ak-1ak

...

ck = a1a2 ..ak

如果你展开多项式(x-a1)…(x-ak)系数正好是c1，…， ck -见Viète的公式。由于每个多项式因子都是唯一的(多项式环是欧几里得域)，这意味着ai是唯一确定的，直到排列为止。

这就证明了记住幂就足以恢复数字。对于常数k，这是一个很好的方法。

However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.

常数k的高级伪代码:

计算给定数的i次幂 相减得到未知数字的i次幂的和。称这些和为bi。 利用牛顿恒等式从bi中计算系数;叫它们ci。c1 = b1;C2 = (c1b1 - b2)/2;详见维基百科的精确公式 因式分解多项式xk-c1xk-1 +…+ ck。 多项式的根是所需的数a1，…正义与发展党。

对于改变k，使用例如Miller-Rabin，找到质数n <= q < 2n，并对所有数字对q进行模数化简来执行步骤。

编辑:这个答案的前一个版本表明，可以使用特征2 (q=2^(log n))的有限域来代替Zq，其中q是素数。但事实并非如此，因为牛顿公式需要除以k以内的数。

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它，比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案，但如果我在这种情况下面临这样的任务(已知边界，低边界)，这是我在现实生活中会使用的解决方案。如果数字集非常大，那么我当然会考虑一个更有效的算法，但在此之前，简单的解决方案对我来说已经足够了。