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

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

你能查一下每个号码是否都存在吗?如果是，你可以试试这个:

S =袋子中所有数字的和(S < 5050) Z =缺失数的和5050 - S

如果缺失的数字是x和y，则:

x = Z - y和 max(x) = Z - 1

所以你检查从1到max(x)的范围，并找到这个数字

你可以通过阅读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.

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

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值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

你已经知道这个和了，a + b = S1。

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。