协慌网

我有一段时间有一个有趣的面试经历。问题开始很简单：

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.

所以这里的问题很简单：

• 你会如何解决Q2 ？
• 你会如何解决Q3 ？
• 你怎么解决Qk ？

澄清

• 通常有 1 个N 的 N 个数字，而不仅仅是 1..100。
• 我不是在寻找明显的基于集合的解决方案，例如使用比特集 ，通过指定比特的值对每个数字的存在 / 不存在进行编码，因此在附加空间中使用O(N)比特。我们无法承受与N成比例的任何额外空间。
• 我也不是在寻找明显的排序优先方法。这个和基于集合的方法在一次采访中值得一提（它们易于实现，并且取决于N ，可能非常实用）。我正在寻找圣杯解决方案（可能或可能不实用，但仍然具有所需的渐近特征）。

所以，当然你必须在O(N)扫描输入，但是你只能捕获少量的信息（用k而不是N 来定义），然后必须以某种方式找到k 个缺失的数字。

以下是Dimitris Andreou 链接的摘要。

记住 i 次幂的总和，其中 i = 1,2，...，k。这减少了求解方程组的问题

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

使用牛顿的身份 ，知道 b _i允许计算

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

如果扩展多项式（xa ₁ ）...（xa _k ），系数将精确地为 c ₁ ，...，c _k - 请参阅Viète 的公式 。由于每个多项式因子唯一（多项式环是欧几里德域 ），这意味着_i是唯一确定的，直到排列。

这结束了一个证据，即记住功率足以恢复数字。对于常数 k，这是一个很好的方法。

然而，当 k 变化时，计算 c ₁ ，...，c _k的直接方法是非常昂贵的，因为例如 c _k是所有缺失数的乘积，幅度为 n！/（nk）！。为了克服这一点， 在 Z _q字段中执行计算 ，其中 q 是素数，使得 n <= q <2n - 它由Bertrand 的假设存在。证明不需要改变，因为公式仍然成立，并且多项式的因子分解仍然是唯一的。您还需要一种用于有限域分解的算法，例如Berlekamp或Cantor-Zassenhaus 的算法 。

常数 k 的高级伪代码：

• 计算给定数字的第 i 个幂
• 减去得到未知数的第 i 个幂的总和。拨打总和 b _i 。
• 使用牛顿的恒等式来计算 b _{i 的}系数; 叫他们_我 。基本上，c ₁ = b ₁ ; c ₂ =（c ₁ b ₁ -b ₂ ）/ 2; 请参阅维基百科的确切公式
• 因子多项式 x ^k -c ₁ x ^k-1 + ... + c _k 。
• 多项式的根是所需的数字 a ₁ ，...，a _k 。

对于变化的 k，使用例如 Miller-Rabin 找到素数 n <= q <2n，并执行所有以 q 为模的数量减少的步骤。

编辑：该答案的先前版本表明，代替 Z _q ，其中 q 是素数，可以使用特征 2 的有限域（q = 2 ^（log n））。情况并非如此，因为牛顿的公式需要按数字除以 k。

你可以通过阅读Muthukrishnan的几页来找到它- 数据流算法：拼图 1：找到丢失的数字 。 它显示了您正在寻找的概括 。这可能是你的面试官阅读的内容以及他提出这些问题的原因。

现在，如果只有人们会开始删除被 Muthukrishnan 治疗所包含或取代的答案，并使这个文本更容易找到。 :)

另请参阅sdcvvc 的直接相关答案 ，其中还包括伪代码（欢呼！无需阅读那些棘手的数学公式:)）（谢谢， 干得好！）。

我们可以通过将数字本身和数字的平方相加来求解 Q2。

然后我们可以将问题减少到

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y是总和低于预期值的程度。

替代给了我们：

(x-k2)^2 + k2^2 = y

然后我们可以解决以确定我们缺少的数字。