不久前我有一次有趣的工作面试经历。问题一开始就很简单：
Q1：我们有一个袋子，里面装着编号
1，2，3，…，100。每个数字只显示一次，因此有100个数字。现在，从袋子中随机抽取一个数字。找到丢失的号码
当然，我以前听过这个面试问题，所以我很快回答了以下问题：
A1：嗯，数字的总和
1+2+3+…+N是（N+1）（N/2）（参见维基百科：算术级数之和）。对于N=100，总和为5050因此，如果包中有所有数字，则总和将正好为
5050。因为缺少一个数字，所以总和将小于这个数字，差值就是这个数字。所以我们可以在O（N）时间和O（1）空间中找到缺失的数字
在这一点上，我认为我做得很好，但突然问题发生了意想不到的转变：
Q2：这是正确的，但是现在如果缺少两个数字，您会怎么做呢
我以前从未见过/听到/考虑过这种变化，所以我惊慌失措，无法回答这个问题。面试官坚持要了解我的思维过程，所以我提到，也许我们可以通过与预期产品进行比较来获得更多信息，或者在收集了第一遍的信息后再进行第二遍，等等，但我真的只是在黑暗中拍摄，而不是真正有一个明确的解决办法
面试官确实试图鼓励我说，第二个等式确实是解决问题的一种方法。在这一点上，我有点心烦意乱（因为之前不知道答案），并问这是一种通用的编程技术（阅读：“有用的”）还是仅仅是一个技巧/抓住答案
面试官的回答让我很惊讶：你可以概括这个技巧，找出3个缺失的数字。事实上，您可以对其进行推广以查找k缺失的数字
Qk：如果包中缺少确切的k数字，您如何有效地找到它
这是几个月前的事了，我仍然不知道这是什么技术。显然存在一个Ω（N）时间下限，因为我们必须至少扫描所有数字一次，但采访者坚持认为，求解技术的时间和空间复杂性（减去O（N）时间输入扫描）是在k中定义的，而不是N
所以这里的问题很简单：
- 您将如何解决第二季度的问题
- 您将如何解决第三季度的问题
- 您将如何解决Qk问题
澄清
- 一般来说，1..N中有N，而不仅仅是1..100
- 我不是在寻找明显的基于集合的解决方案，例如，使用一个位集合，通过指定位的值对每个数字的存在/不存在进行编码，因此在额外的空间中使用
O（N）位。我们负担不起任何与N成比例的额外空间 - 我也不是在寻找明显的排序优先的方法。这一点和基于集合的方法值得在访谈中提及（它们易于实现，并且取决于N，可能非常实用）。我正在寻找圣杯解决方案（它可能实现起来很实用，也可能实现起来不实用，但仍然具有所需的渐进特性）
因此，当然您必须再次扫描O（N）中的输入，但您只能捕获少量信息（定义为k而不是N），然后必须以某种方式找到k缺失的数字
下面是Dimitris Andreou链接的摘要
记住i次方之和，其中i=1,2，…，k。这将问题简化为求解方程组
a1+a2+…+ak=b1
a12+a22+…+ak2=b2
a1k+a2k+…+akk=bk
利用牛顿恒等式，知道bi可以计算
c1=a1+a2+。。。ak
c2=a1a2+a1a3+…+ak-1ak
ck=a1a2。。。ak
如果展开多项式（x-a1）…（x-ak），则系数将精确为c1，…，ck-参见Viète的公式。由于每个多项式因子都是唯一的（多项式环是欧几里德域），这意味着ai是唯一确定的，直到置换
这就结束了一个证明：记住幂就足以恢复数字。对于常数k，这是一个很好的方法
然而，当k变化时，计算c1，…，ck的直接方法是非常昂贵的，因为例如ck是所有缺失数的乘积，数量级n/（n-k）！。为了克服这个问题，在Zq字段中执行计算，其中q是质数，使得n<；=q<；2n-根据伯特兰的假设，它是存在的。证明不需要改变，因为公式仍然成立，多项式的因式分解仍然是唯一的。您还需要有限域上的因式分解算法，例如Berlekamp或Cantor Zassenhaus的算法
常数k的高级伪码：
- 计算给定数字的i次方
- 减法得到未知数的i次方和。调用总和bi
- 使用牛顿恒等式从bi计算系数；叫他们ci。基本上，c1=b1；c2=（c1b1-b2）/2；有关精确公式，请参见维基百科
- 多项式xk-c1xk-1+…+ck
- 多项式的根是所需的数字a1，…，ak
对于变化的k，找到一个素数n<；=q<；2n使用例如Miller-Rabin，并使用所有减少的模数q执行步骤
编辑：该答案的前一版本指出，可以使用特征2（q=2^（logn））的有限域，而不是Zq，其中q是素数。事实并非如此，因为牛顿公式要求除以k以下的数