前一段时间我有一次有趣的面试经历。这个问题开始很容易：

Q1：我们有一个包含数字的包1 ， 2 ， 3 ，...， 100 。每个数字仅出现一次，因此有 100 个数字。现在，从袋子中随机抽取一个号码。查找丢失的号码。

我当然已经听过这个面试问题，所以我很快就回答了以下问题：

A1 ：嗯，数字1 + 2 + 3 + … + N的总和为(N+1)(N/2) （请参阅Wikipedia：算术级数之和 ）。对于N = 100 ，总和为5050 。

因此，如果袋子中所有数字都存在，则总和为5050 。由于缺少一个数字，所以总和小于这个数字，而差就是那个数字。因此我们可以找到O(N)时间和O(1)空间中的缺失数。

在这一点上，我认为我做得不错，但是突然之间，这个问题突然发生了变化：

Q2 ：是的，但是现在如果缺少两个数字，您将如何处理？

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

面试官的确通过说第二个方程式确实是解决问题的一种方式来鼓励我。在这一点上，我有点不高兴（因为事先不知道答案），问我这是否是一种通用的（读作：“有用的”）编程技术，还是仅仅是一个技巧 / 陷阱。

面试官的回答让我感到惊讶：您可以推广该技术以找到 3 个缺失的数字。实际上，您可以对其进行概括以找到k 个缺失数字。

Qk ：如果袋子中恰好缺少k 个数字，您将如何有效地找到它？

这是几个月前，但我仍然不知道这种技术是什么。显然，存在一个Ω(N)时间下限，因为我们必须至少扫描一次所有数字，但是访调员坚持认为，求解技术的TIME和SPACE复杂度（减去O(N)时间输入扫描）定义为k不是N。

所以这里的问题很简单：

• 您将如何解决Q2 ？
• 您将如何解决第 3 季度 ？
• 您将如何解决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 公式 。由于每个多项式因子都是唯一的（多项式的环是一个欧几里德域 ），因此这意味着 a _i是唯一确定的，直到置换。

这样就证明了记忆力足以恢复数字。对于常数 k，这是一个好方法。

然而，当 k 变化时，直接计算 c ₁ ，...，c _{k 的方法}是非常昂贵的，因为例如，c _k是所有缺失数 n 1 /（nk）1 的乘积。为了克服这个问题，请在 Z _q字段中执行计算 ，其中 q 是质数，使得 n <= q <2n - 根据Bertrand 的假设存在。由于公式仍然成立，并且多项式的因式分解仍然是唯一的，因此无需更改证明。您还需要一种用于对有限域进行因子分解的算法，例如Berlekamp或Cantor-Zassenhaus 提出的算法 。

常数 k 的高级伪代码：

• 计算给定数字的第 i 次幂
• 减去可得到未知数的第 i 次幂。求和 b _i 。
• 使用牛顿的恒等式从 b _i计算系数；称他们为 c _i 。基本上，c ₁ = b ₁ ； c ₂ ＝（c ₁ b ₁ -b ₂ ）/ 2；有关详细公式，请参阅 Wikipedia
• 分解多项式 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

然后我们可以解决以确定丢失的数字。

正如 @j_random_hacker 指出的那样，这与在 O（n）时间和 O（1）空间中查找重复项非常相似， 在那里对我的答案进行修改也可以在这里工作。

假设 “bag” 由大小为N - k的基于 1 的数组A[] N - k ，我们可以在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额外的条目初始化为与数组中的第一个条目相同（这只是一个方便的值，我们知道该值已经存在于数组中 - 在此步骤之后，初始大小数组中缺少的任何条目扩展数组中仍然缺少Nk ）。

第二个循环置换扩展数组，以便如果元素x至少存在一次，则这些条目之一将在位置A[x] 。

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

第三个循环将打印数组i中未被值i占用的索引 - 这意味着i一定已经丢失了。

我请一个 4 岁的孩子解决这个问题。他对数字进行了排序，然后继续计数。它的空间要求为 O（厨房地板），并且工作原理很简单，但是缺少许多球。

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

我喜欢简单的解决方案 - 甚至我相信，这可能比计算总和或平方和等速度要快。

我还没有检查数学，但我怀疑在计算Σ(n^2)的同一遍中计算Σ(n^2) Σ(n)是否可以提供足够的信息来获取两个缺失的数字，如果也要进行Σ(n^3)一共有三个，依此类推。

基于数字和的解决方案存在的问题是它们没有考虑存储和处理具有大指数的数字的成本... 在实践中，因为它适用于非常大的 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))此算法更直观，具有相同的时间复杂度并且使用较少的空间。

等一下。如问题所述，袋子里有 100 个数字。无论 k 有多大，都可以在固定时间内解决该问题，因为您可以使用一个集合并最多在一个循环中进行 100-k 次迭代从集合中删除数字。 100 是常数。剩余数字集就是您的答案。

如果我们将解决方案推广到从 1 到 N 的数字，则除 N 不是常数外，没有任何变化，因此我们处于 O（N-k）= O（N）时间。例如，如果使用位集，则在 O（N）时间中将位设置为 1，迭代数字，然后将位设置为 0（O（Nk）= O（N）），然后有答案。

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

要解决 2（和 3）个缺失数字的问题，您可以修改quickselect ，它平均在O(n)运行，如果就地进行分区，则使用常量内存。

1. 相对于随机枢轴p将集合划分为分区l和r ，分区l包含小于枢轴的数字， r包含大于枢轴的数字。

2. 通过将枢轴值与每个分区的大小进行比较，确定 2 个缺失数字所在的分区（ p - 1 - count(l) = count of missing numbers in l和n - count(r) - p = count of missing numbers in r p - 1 - count(l) = count of missing numbers in l n - count(r) - p = count of missing numbers in r ）

3. a）如果每个分区缺少一个数字，则使用总和差法查找每个丢失的数字。

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1和((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b）如果一个分区缺少两个数字并且该分区为空，则丢失的数字为(p-1,p-2)或(p+1,p+2)具体取决于哪个分区缺少数字。

   如果一个分区缺少 2 个数字但不为空，则递归到该分区。

由于只有 2 个缺失数字，因此该算法始终丢弃至少一个分区，因此保留了快速选择的O(n)平均时间复杂度。同样，对于 3 个丢失的数字，该算法每次通过还会丢弃至少一个分区（因为 2 个丢失的数字，最多只有 1 个分区将包含多个丢失的数字）。但是，我不确定添加更多丢失的数字后性能会下降多少。

这是一个不使用就地分区的实现，因此此示例不满足空间要求，但确实说明了算法的步骤：

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

演示版