前段时间我有一次有趣的面试经历。问题一开始很简单:
Q1:我们有一个袋子，里面有数字1,2,3，…，100。每个数字恰好出现一次，所以有100个数字。现在从袋子里随机抽取一个数字。找到丢失的号码。
当然，我以前听过这个面试问题，所以我很快就回答了这个问题:
A1:嗯，1 + 2 + 3 +…+ N的和是(N+1)(N/2)(参见维基百科:等差级数的和)。当N = 100时，和是5050。
因此，如果所有的数字都在袋子里，总和将恰好是5050。因为少了一个数，总和就会小于这个数，差的就是这个数。所以我们可以在O(N)时间和O(1)空间中找到这个缺失的数。
在这一点上，我认为我做得很好，但突然间，问题发生了意想不到的转变:
这是正确的，但是如果少了两个数字，你会怎么做?
我以前从未见过/听过/考虑过这种变化，所以我很恐慌，无法回答这个问题。面试官坚持要知道我的思考过程，所以我提到，也许我们可以通过与预期产品进行比较来获得更多信息，或者在从第一次传递中收集到一些信息后再进行第二次传递，等等，但我真的只是在黑暗中拍摄，而不是真正有一个明确的解决方案的路径。
面试官试图鼓励我说，有第二个方程确实是解决问题的一种方法。在这一点上，我有点不安(因为事先不知道答案)，并问这是一种通用的(阅读:“有用的”)编程技术，还是只是一个技巧/答案。
面试官的回答让我惊讶:你可以把这个技巧概括为3个缺失的数字。事实上，你可以推广它来找到k个缺失的数。
Qk:如果袋子里少了k个数字，你如何有效地找到它?
这是几个月前的事了，我还不明白这个技巧是什么。显然有一个Ω(N)的时间下限，因为我们必须扫描所有的数字至少一次，但面试官坚持认为，解决技术的时间和空间复杂度(减去O(N)次输入扫描)定义为k而不是N。
所以问题很简单:
如何解决Q2?
你会如何解决Q3?
如何求解Qk?
澄清
Generally there are N numbers from 1..N, not just 1..100.
I'm not looking for the obvious set-based solution, e.g. using a bit set, encoding the presence/absence each number by the value of a designated bit, therefore using O(N) bits in additional space. We can't afford any additional space proportional to N.
I'm also not looking for the obvious sort-first approach. This and the set-based approach are worth mentioning in an interview (they are easy to implement, and depending on N, can be very practical). I'm looking for the Holy Grail solution (which may or may not be practical to implement, but has the desired asymptotic characteristics nevertheless).
当然，你必须以O(N)为单位扫描输入，但你只能捕获少量的信息(用k而不是N定义)，然后必须以某种方式找到k个缺失的数字。
我们可以用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.
请注意，如上所述，上面提供的两个并行算法可能需要额外的空间。
下面是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以内的数。
