不久前，我有一次有趣的求职面试经历。这个问题开始很容易：

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

同样，您当然必须扫描 中的输入O(N)，但您只能捕获少量信息（根据k而不是N定义），然后必须以某种方式找到k缺失的数字。