简单的面试问题变得更难了：给定1到100的数字，找出缺失的数字（s），确定恰好有k个数字丢失。

Question

我曾经有过一次有趣的工作面试经历。问题开始非常简单：

Q1：我们有一个装着数字 1、2、3、……、100 的袋子。每个数字恰好出现一次，因此总共有 100 个数字。现在从袋子里随机取出一个数字，请找到缺失的数字。

当然，我之前听过这个面试问题，所以我很快回答道：

A1：嗯，数字 1 + 2 + 3 + … + N 的和是 (N+1)(N/2)（参见 Wikipedia: sum of arithmetic series）。对于 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个缺失的数字。

- polygenelubricants

---

谢谢您的澄清。从一开始就说清楚“我正在寻找一个算法，它的时间复杂度为O(N)，空间复杂度为O(K)，其中K是缺失数字的数量”就好了；-) - Dave O.

在Q1的陈述中，您应该明确指出您无法按顺序访问数字。这对您来说可能很明显，但我从未听说过这个问题，而“袋子”这个术语（也表示“多重集合”）有点令人困惑。 - Jérémie

请阅读以下内容，因为这里提供的答案荒谬可笑：https://dev59.com/sG855IYBdhLWcg3wViot - Matthieu N.

将数字求和的解决方案需要log(N)的空间，除非您认为无限整数的空间要求为O(1)。但是，如果允许使用无限整数，那么您只需要一个整数就可以拥有任意多的空间。 - Udo Klein

顺便提一下，Q1的另一个不错的替代解决方案是计算从1到n所有数字的异或值，然后将结果与给定数组中的所有数字进行异或运算。最后就能得到缺失的数字。在这个解决方案中，您无需担心溢出问题，就像求和时需要考虑的那样。 - sbeliakov

Answer 1

这里是Dimitris Andreou的link的摘要。

记住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-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)!。为了克服这个问题，在Z_q域中执行computations，其中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，使用例如Miller-Rabin找到小于等于q且大于n的素数n，并将所有数字模q缩小执行步骤。

编辑：此答案的先前版本说明可以使用特征为2（q=2^(log n)）的有限域，而不是质数q的Z_q。这不是情况，因为牛顿公式需要除以最多k个数字。

- sdcvvc

---

不一定需要使用素域，也可以使用 q = 2^(log n)。 （你是如何制作上、下标的？！） - Heinrich Apfelmus

这真的非常聪明。与此同时，值得怀疑的是，是否真的值得花费这样的精力，或者（部分）这个解决方案针对一个相当人为的问题能否以其他方式被重复利用。即使这是一个现实世界中的问题，在许多平台上，最琐碎的“O（N ^ 2）”解决方案可能会在相当高的“N”下超过这个美丽的算法。这让我想起了这个链接：http://tinyurl.com/c8fwgw 不过还是很棒的工作！我没耐心去看所有的数学 :) - back2dos

我认为这是一个很棒的回答。我认为这也说明了如果将缺失的数字扩展到1以外会成为一个多么不好的面试问题。即使第一个也有点像“陷阱”，但它已经足够常见，基本上表明“你做了一些面试准备”。但是期望一个计算机科学专业的人能够在面试中突破k=1（特别是“即兴”），有点儿可笑。 - corsiKa

这实际上是对输入进行Reed Solomon编码。 - David Ehrmann

我认为，在一个哈希集合中输入所有数字，并使用查找来确定缺失的数字，循环遍历整个1...N序列，这将是最常见、平均速度最快（对于k变化而言）、最易于调试和维护、最容易理解的解决方案。当然，使用数学方法也很厉害，但在处理业务时，你需要成为一名工程师而不是一名数学家。 - v.oddou

Answer 2

你可以通过阅读 Muthukrishnan - 数据流算法：难题一：查找缺失数字 的前几页找到答案。这本书恰好展示了你正在寻找的通用方法。很可能这就是你的面试官所读的内容，也是他提出这些问题的原因。

此外，还请参考sdcvvc的相关回答，其中包括伪代码（太棒了！无需阅读那些棘手的数学公式 :)) （谢谢，干得好！）。

- Dimitris Andreou

---

哦...这很有趣。我必须承认，数学让我有点困惑，但我只是匆匆浏览了一下。可能稍后再打开看看。 :) 另外+1以使此链接更易于查找。;-) - Chris

谷歌图书链接对我不起作用。这里有一个更好的版本[PostScript 文件]，请访问链接：http://www.cs.rutgers.edu/~muthu/stream-1-1.ps。 - Heinrich Apfelmus

哇，我没想到这个会被点赞！上次我发布了一个解决方案的参考（那时是 Knuth 的），而不是自己尝试解决，结果反而被踩了：https://dev59.com/UnA75IYBdhLWcg3w3NLf#3077753我内心的图书管理员对此感到欣喜，谢谢 :) - Dimitris Andreou

@Apfelmus，注意这只是一个草稿。（当然我不怪你，我也在找到这本书之前将草稿和真正的东西混淆了近一年）。顺便说一句，如果链接无法使用，您可以访问http://books.google.com/并搜索“Muthukrishnan数据流算法”（不带引号），它是第一个弹出的。 - Dimitris Andreou

请阅读以下内容，因为这里提供的答案荒谬可笑：https://dev59.com/sG855IYBdhLWcg3wViot - Matthieu N.

这本书说最佳空间限制是 k^2 logn 位，使用随机分解算法？这不就是通过将 {1,...,n} -> {1,...,k^2} 进行哈希得到的结果吗？我添加了一个包含此解决方案的答案。至少对于计算机科学家来说，这应该是最明显的选择。 - Thomas Ahle

Answer 3

我们可以通过将这两个数字本身和它们的平方值相加来解决 Q2 问题。

然后，我们可以将问题简化为：

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

其中x和y表示总和低于期望值的距离。

代入公式得：

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

然后我们可以解决这个方程以确定缺失的数字。

- Anon.

---

+1；我在Maple中尝试了选定数字的公式，它有效。但是，我仍然无法说服自己它为什么有效。 - polygenelubricants

如果你想证明正确性，首先需要展示它总是提供 一个 正确的解决方案（也就是说，它总是产生一对数字，当将它们从集合中移除后，剩下的数字和与平方和相等）。然后，证明唯一性就简单了，只需证明它只产生这样一对数字即可。 - Anon.

这个方程的特性意味着你将从它得到两个k2的值。然而，从你用来生成k1的第一个方程可以看出，这两个k2的值意味着k1是另一个值，因此你会得到两个解，其实是同样的数字反过来。如果你随便声明k1>k2，那么二次方程只有一个解，因此整个问题只有一个解决方案。显然，由于问题的性质总是存在答案，所以它总是有效的。 - Chris

给定一个数的和 k1+k2，会有很多对。我们可以将这些对写成 K1=a+b 和 K2=a-b 的形式，其中 a=(K1+K2/2)。对于给定的和，a 是唯一的。平方和 (a+b)*2 + (a-b)2 = 2(a*2 + b*2)。对于给定的和 K1+K2，a2 项是固定的，由于 b2 项的存在，我们看到平方和将是唯一的。因此，值 x 和 y 对于一对整数来说是唯一的。 - phkahler

太棒了！@user3281743 这是一个例子。让缺失的数字（k1和k2）是4和6。Sum(1 -> 10) = 55 和 Sum(1^2 -> 10^2) = 385。现在让 x = 55 - (所有剩余数字之和)，y = 385 - (所有剩余数字的平方之和)，因此 x = 10，y = 52。按照所示进行代换，我们得到：(10 - k2)^2 + k2^2 = 52，你可以简化为：2k^2 - 20k + 48 = 0。解二次方程得出答案为4和6。 - AlexKoren

Answer 4

我让一个四岁的孩子解决这个问题。他把数字排序然后数过来。这种方法需要 O(厨房地板大小) 的空间，而且无论有多少球缺失都一样容易实现。

- Colonel Panic

---

你的四岁孩子可能快要五岁了，或者是个天才。而我的四岁女儿甚至还不能正确地数到4。公平地说，她现在才勉强掌握了“4”的存在。否则一直会跳过它，数数会变成“1、2、3、5、6、7”。我让她把铅笔加起来，她只能通过重新从头开始数来做到1+2=3。我实际上很担心...:'( 啊。。 - v.oddou

哈哈，但这不会是O(n^2)吗？（针对“厨房地板”进行笑话/调侃，但表达的意思可能需要更具上下文才能准确理解。对于问题中的数学术语，“O(n^2)”可能指代一种时间复杂度的算法分析方式。） - user3235832

O(m²) 我猜 :) - Viktor Mellgren

排序绝对不是O(n)。 - phuclv

答案中提到：“这需要 O（厨房地板面积）的空间。” 但无论如何，这是一种情况，其中排序可以在O（n）时间内完成 - 请参阅此讨论。 - Anthony Labarre

Answer 5

正如@j_random_hacker所指出的，这与在O(n)时间和O(1)空间中找到重复项非常相似，我在那里的答案也适用于这里。

假设"bag"由大小为N-k的基于1的数组A[]表示，我们可以在O(N)时间和O(k)额外空间内解决Qk。

首先，我们通过添加k个元素来扩展数组A[]，使其现在的大小为N。 这是O(k)的额外空间。 然后我们运行以下伪代码算法：

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化了"k"个额外的条目，使它们与数组中的第一个条目相同（这只是一个方便的值，我们知道它已经存在于数组中 - 在此步骤之后，任何在大小为"N-k"的初始数组中缺失的条目仍然缺失于扩展数组中）。

第二个循环对扩展数组进行排列，以便如果元素"x"至少出现一次，则其中一个条目将位于位置"A[x]"。

请注意，尽管它有嵌套循环，但它仍在O(N)时间内运行 - 仅当存在i满足"A[i]!=i"时，交换才会发生，每个交换都至少设置一个元素，使得"A[i]==i"，在此之前不是这样。这意味着交换的总数（因此循环体的总执行次数）最多为N-1。

第三个循环打印数组索引"i"未被值"i"占用的索引 - 这意味着"i"必须缺失。

- caf

---

我不明白为什么如此少的人投票支持这个答案，甚至没有将其标记为正确答案。这是Python代码。它以O(n)时间运行，并需要额外的空间O(k)。http://pastebin.com/9jZqnTzV - wall-e

这与设置位并计算位为0的位置非常相似。由于您正在创建一个整数数组，因此会占用更多内存。 - Fox

“设置位并计算位值为0的位置”需要额外O(n)的空间，这个解决方案展示了如何使用额外O(k)的空间。 - caf

不能处理流式输入并会修改输入数组（尽管我非常喜欢它并且这个想法很有成效）。 - comco

不，这没问题。交换将更改A[i]，这意味着下一次迭代将不会比较与上一次相同的两个值。新的A[i]将与上一个循环的A[A[i]]相同，但新的A[A[i]]将是一个新的值。试试看吧。 - caf

Answer 6

不确定这是否是最有效的解决方案，但我会遍历所有条目，并使用位集来记住哪些数字已设置，然后测试0位。

我喜欢简单的解决方案 - 我甚至相信它可能比计算总和或平方和等更快。

- Chris Lercher

---

我曾提出这个显而易见的答案，但这不是面试官想要的。我在问题中明确表示这不是我想要的答案。另一个显而易见的答案是：首先进行排序。无论是O(N)计数排序还是O(N log N)比较排序都不是我想要的，虽然它们都是非常简单的解决方案。 - polygenelubricants

@polygenelubricants：我在你的问题中找不到你说的地方。如果您认为bitset是结果，那么就没有第二遍了。复杂度是（如果我们将N视为常数，正如面试官所建议的那样，复杂度是“在k中定义而不是N”）O(1)，如果您需要构建更“干净”的结果，则获得O(k)，这是您可以获得的最佳结果，因为您总是需要O(k)来创建干净的结果。 - Chris Lercher

@hmt: 是的，这个问题在几分钟前被编辑过。我只是提供一个回答，这是我期望从面试者那里得到的...人为构造次优解（无论你做什么，你都不能击败O(n)+ O(k)时间复杂度）对我来说没有意义 - 除非你负担不起额外的O(n)空间，但问题并没有明确说明。 - Chris Lercher

我已经再次编辑了问题以进一步澄清。我非常感谢您的反馈/答案。 - polygenelubricants

实际上，你可以在这样一个明确定义的列表上清楚地进行桶排序，其时间复杂度为O(n)，而不是n log n。 - Tatarize

Answer 7

我没有检查过数学，但我怀疑在计算Σ(n)的同时计算Σ(n^2)将提供足够的信息来获取两个缺失的数字，如果有三个数字，则也需要计算Σ(n^3)等等。

- AakashM

Answer 8

基于数字和的解决方案存在一个问题，它们没有考虑到存储和处理具有大指数的数字的成本...实际上，为了使其适用于非常大的n，将使用大数字库。我们可以分析这些算法的空间利用率。

我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度。

存储：

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

因此，l_j \in \Theta(j log n)

使用的总存储量：\sum_{j=1}^k l_j \in \Theta(k^2 log n)

使用的空间：假设计算a^j需要ceil(log_2 j)时间，则总时间：

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

总用时: \Theta(kn log n)

如果这个时间和空间都可以接受，您可以使用一个简单的递归算法。让b!i成为袋子中第i个条目，n是删除之前数字的数量，k是删除的数量。在Haskell语法中...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

存储使用: 列表为O(k)，栈为O(log(n)): O(k + log(n)) 该算法更直观，时间复杂度相同，且使用更少的空间。

- a1kmm

---

+1，看起来不错，但是在代码片段#1的第4行到第5行之间我有点迷糊了——你能再解释一下吗？谢谢！ - j_random_hacker

isInRange 的时间复杂度为 _O(log n)_，而不是 _O(1)_：它比较的是在 1..n 范围内的数字，因此必须比较 O(log n) 位。我不知道这个错误对其余分析的影响程度。 - jcsahnwaldt Reinstate Monica

Answer 9

对于 Q2 的一个非常简单的解决方案，我很惊讶为什么没有人回答过。使用 Q1 中的方法来找到两个缺失数字的和。我们用 S 来表示它，那么其中一个缺失数字小于 S/2，另一个大于 S/2（显然）。将所有从 1 到 S/2 的数字相加，并将其与公式的结果进行比较（类似于 Q1 中的方法），以找到较小的缺失数字。从 S 中减去它即可得到较大的缺失数字。

- Gilad Deutsch

---

我认为这与Svalorzen的答案相同，但你用更好的措辞解释了它。你有没有想过如何将其推广到Qk？ - John McClane

抱歉错过了另一个答案。我不确定是否可以将其推广到$Q_k$，因为在这种情况下，您无法将最小的缺失元素限制在某个范围内。您确实知道某些元素必须小于$S/k$，但对于多个元素可能也是如此。 - Gilad Deutsch

Q_k怎么样：在取平均值后二分，同时在二分的一侧计算加数总和，您将知道每侧缺少的数字数量 - 问题已经被减少到左侧的Q_l和右侧的Q_r，其中l + r = k，其中l < k且r < k，原因与答案相同 - 因此可以递归地解决这些问题。 - Tarje Bargheer

Answer 10

请稍等。根据问题陈述，袋子里有100个数字, 无论k有多大，都可以在常数时间内解决问题，因为您可以使用一个集合并在不超过100-k次循环迭代中从集合中删除数字。100是一个常数。剩余数字的集合就是答案。

如果将解决方案推广到1到N的数字上，则除了N不是常数外，其他什么也没有变化，因此我们在O（N-k）= O（N）时间内。例如，如果我们使用位集，我们可以在O（N）时间内将位设置为1，遍历数字，在我们进行迭代时将位设置为0（O（N-k）= O（N）），然后我们得到答案。

我认为面试官问你如何以O（k）时间打印最终集合的内容，而不是以O（N）时间。显然，对于位集，您必须遍历所有N位才能确定是否应该打印数字。但是，如果更改集合的实现方式，则可以在k次迭代中打印出数字。这是通过将数字放入对象中存储在哈希集和双向链接列表中来完成的。当您从哈希集中删除对象时，您还会从列表中删除它。答案将留在长度为k的列表中。

- JeremyP

---

这个答案太简单了，我们都知道简单的答案行不通！;) 但说真的，原问题可能应该强调O(k)空间要求。 - DK.

问题不在于简单，而是你需要使用O(n)的附加内存来进行映射。这个问题应该在恒定时间和恒定内存中得到解决。 - Mojo Risin

我可以证明最小解至少为O(N)。因为如果小于O(N)，那意味着你甚至没有看过一些数字，而且由于没有指定顺序，查看所有数字是强制性的。 - v.oddou

如果我们将输入视为流，并且n太大而无法保存在内存中，则O(k)的内存需求是有意义的。尽管如此，我们仍然可以使用哈希：只需创建k^2个桶并对每个桶使用简单的求和算法即可。这只需要k^2的内存，还可以使用更多的桶来获得高成功率。 - Thomas Ahle