arrays - 简单的面试问题变得更难了 : given numbers 1. .100，找到恰好 k 丢失的缺失数字

Question

前段时间我有一次有趣的求职面试经历。问题开始很简单:

Q1: We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.

当然，我以前听过这个面试问题，所以我很快按照以下思路回答:

A1: Well, the sum of the numbers 1 + 2 + 3 + … + N is (N+1)(N/2) (see Wikipedia: sum of arithmetic series). For N = 100, the sum is 5050.

Thus, if all numbers are present in the bag, the sum will be exactly 5050. Since one number is missing, the sum will be less than this, and the difference is that number. So we can find that missing number in O(N) time and O(1) space.

到这里我以为自己做的很好了，没想到问题突然来了个转折:

Q2: That is correct, but now how would you do this if TWO numbers are missing?

我以前从未见过/听说过/考虑过这种变化，所以我 panic ，无法回答这个问题。面试官坚持要知道我的思维过程，所以我提到也许我们可以通过与预期产品进行比较来获得更多信息，或者在从第一遍收集到一些信息后进行第二遍等，但我真的只是在拍摄在黑暗中，而不是真正有一条通向解决方案的清晰路径。

面试官确实试图鼓励我，说有第二个方程确实是解决问题的一种方法。在这一点上，我有点不高兴(因为事先不知道答案)，并询问这是一种通用的(读作:“有用的”)编程技术，还是只是一个技巧/陷阱答案。

面试官的回答让我很吃惊:你可以推广找到 3 个缺失数字的技术。事实上，您可以将其概括为找到 k 个缺失的数字。

Qk: If exactly k numbers are missing from the bag, how would you find it efficiently?

这是几个月前的事了，我还是想不通这是什么技术。显然有一个 Ω(N) 时间下限，因为我们必须至少扫描所有数字一次，但面试官坚持认为 TIME 和 SPACE 求解技术的复杂性(减去 O(N) 时间输入扫描)定义为 k 而不是 N。

所以这里的问题很简单:

• 您将如何解决Q2？
• 您将如何解决Q3？
• 你会如何解决Qk？

---

说明

• 通常有 N 个数字来自 1..N，而不仅仅是 1..100。
• 我不是在寻找明显的基于集合的解决方案，例如使用 bit set ，通过指定位的值对每个数字的存在/不存在进行编码，因此在额外空间中使用 O(N) 位。我们负担不起任何与 N 成正比的额外空间。
• 我也不是在寻找明显的排序优先方法。这个和基于集合的方法在面试中值得一提(它们很容易实现，并且取决于N，可以非常实用)。我正在寻找 chalice 解决方案(实现起来可能实用也可能不实用，但仍然具有所需的渐近特性)。

所以，同样，您当然必须在 O(N) 中扫描输入，但您只能捕获少量信息(根据 k 而非 < em>N)，然后必须以某种方式找到 k 个缺失的数字。

Answer 1

这是 Dimitris Andreou's 的摘要link .

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

a₁ + a₂ + ... + a_k = b₁

a₁² + a₂² + ... + a_{k2 = b2}

...

a₁^k + a₂^k + ... + a_k^k = b_k

使用 Newton's identities , 知道 b_i 允许计算

c₁ = a₁ + a₂ + ... a_k

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

...

c_k = a₁a₂ ... a_k

如果展开多项式 (x-a₁)...(x-a_k) 系数将正好是 c₁, .. ., c_k - 参见 Viète's formulas .由于每个多项式因子都是唯一的(多项式环是一个 Euclidean domain )，这意味着 a_i 是唯一确定的，直至排列。

这结束了内存力足以恢复数字的证明。对于常量 k，这是一个很好的方法。

但是，当 k 变化时，直接计算 c₁,...,c_k 的方法非常昂贵，因为例如c_k 是所有缺失数字的乘积，大小为 n!/(n-k)!。为了克服这个问题，执行 computations in Z_q field ，其中 q 是一个质数，使得 n <= q < 2n - 它存在于 Bertrand's postulate .不需要更改证明，因为公式仍然成立，并且多项式的因式分解仍然是唯一的。您还需要一种用于有限域分解的算法，例如 Berlekamp 的算法或 Cantor-Zassenhaus .

常量 k 的高级伪代码:

• 计算给定数的 i 次方
• 减去未知数的 i 次方的总和。称总和为 b_i。
• 使用牛顿恒等式计算 b_i 的系数；称他们为 c_i。基本上，c₁ = b₁; c₂ = (c₁b₁ - b₂)/2;请参阅维基百科以了解确切的公式
• 因式分解多项式 x^k-c₁x^k-1 + ... + c_k .
• 多项式的根是所需的数字 a₁, ..., a_k。

对于不同的 k，找到一个素数 n <= q < 2n 使用例如Miller-Rabin，并执行所有数字减少模 q 的步骤。

编辑:此答案的前一版本指出，可以使用特征为 2 (q=2^(log n) ).事实并非如此，因为牛顿公式需要除以 k 以内的数字。