简单的面试问题变得更难：给定数字 1..100，找到缺少的数字

以下是 Dimitris Andreou's link 的摘要。

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

a1 + a2 + ... + ak = b1

a12 + a22 + ... + ak2 = b2

...

a1k + a2k + ... + akk = bk

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

c1 = a1 + a2 + ... ak

c2 = a1a2 + a1a3 + ... + ak-1ak

...

ck = a1a2 ... ak

如果您展开多项式 (xa₁)...(xa_k) 系数将恰好是 c₁, ..., c _k - 见 Viète's formulas。由于每个多项式因子都是唯一的（多项式环是 Euclidean domain），这意味着 a_i 是唯一确定的，直到排列。

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

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

常数 k 的高级伪代码：

计算给定数字的 i 次方

减法得到未知数的 i 次方之和。调用总和 bi。

使用牛顿恒等式从 bi 计算系数；称他们为ci。基本上，c1 = b1; c2 = (c1b1 - b2)/2;有关确切公式，请参见 Wikipedia

因式分解多项式 xk-c1xk-1 + ... + ck。

多项式的根是所需的数字 a1, ..., ak。

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

编辑：此答案的先前版本指出，可以使用特征 2 (q=2^(log n)) 的有限域代替 Zq，其中 q 是素数。情况并非如此，因为牛顿公式需要除以不超过 k 的数字。

---

您将通过阅读 Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers 的几页找到它。 它准确地显示了您正在寻找的概括。可能这就是你的面试官读到的内容以及他提出这些问题的原因。

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

---

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

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

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

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

替换给了我们：

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

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

---

正如@j_random_hacker 指出的那样，这与Finding duplicates in O(n) time and O(1) space 非常相似，并且对我的答案的改编也适用于此处。

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

首先，我们将数组 A[] 扩展 k 个元素，使其现在的大小为 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) 时间内运行 - 仅当存在与 A[i] != i 相同的 i 时才会发生交换，并且每个交换设置至少一个与 A[i] == i 相同的元素，其中以前不是这样的。这意味着交换的总数（以及 while 循环体的执行总数）最多为 N-1。

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

---

我请了一个 4 岁的孩子来解决这个问题。他把数字排序，然后一起数。这有 O（厨房地板）的空间要求，并且它的工作同样容易，但是缺少许多球。

---

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

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

---

我没有检查数学，但我怀疑在计算 Σ(n) 的同一遍中计算 Σ(n^2) 会提供足够的信息来获得两个缺失的数字，如果有三个，则执行 Σ(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 的列表中。

---

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

---

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

将集合相对于随机枢轴 p 划分为分区 l，其中包含小于枢轴的数字，以及 r，其中包含大于枢轴的数字。通过将枢轴值与每个分区的大小进行比较来确定 2 个缺失数字所在的分区（p - 1 - count(l) = l 中缺失数字的计数和 n - count(r) - p = 缺失数字的计数在 r) a) 如果每个分区都缺少一个数字，则使用总和的差异方法来查找每个缺少的数字。 (1 + 2 + ... + (p-1)) - sum(l) = 缺失 #1 和 ((p+1) + (p+2) ... + n) - sum(r) = 缺失#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);
    }
  }

Demo

---

对于 Q2，这是一个比其他解决方案效率低一些的解决方案，但仍然具有 O(N) 运行时间并占用 O(k) 空间。

这个想法是两次运行原始算法。在第一个中，您会得到一个缺失的总数，它为您提供了缺失数字的上限。我们称这个号码为 N。您知道缺少的两个数字之和将是 N，因此第一个数字只能在区间 [1, floor((N-1)/2)] 内，而第二个数字将在 [floor(N/2)+1,N-1] 内。

因此，您再次循环所有数字，丢弃未包含在第一个间隔中的所有数字。那些，你跟踪他们的总和。最后，您将知道缺少的两个数字之一，以及第二个。

我有一种感觉，这种方法可以推广，并且可能在单次通过输入期间“并行”运行多个搜索，但我还没有弄清楚如何。

---

这是一个使用 k 位额外存储的解决方案，没有任何巧妙的技巧，而且很简单。执行时间O(n)，额外空间O(k)。只是为了证明这可以在不先阅读解决方案或成为天才的情况下解决：

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

---

动机

如果要解决一般情况问题，并且可以存储和编辑数组，那么 Caf's solution 是迄今为止最有效的。如果您无法存储数组（流式版本），那么 sdcvvc's answer 是当前建议的唯一解决方案类型。

如果您可以存储数组但不能编辑它，我提出的解决方案是最有效的答案（到目前为止，在这个线程上），我从 Svalorzen's solution 中得到了这个想法，它解决了 1 或 2 个丢失的项目。此解决方案需要 Θ(k*n) 时间和 O(min(k,log(n))) 和 Ω(log(k)) 空间。它也适用于并行性。

概念

这个想法是，如果您使用比较总和的原始方法：
sum = SumOf(1,n) - SumOf(array)

...然后你取缺失数字的平均值：
average = sum/n_missing_numbers

...提供了一个边界：在缺失的数字中，保证有至少一个数小于或等于average，和 在至少比 average 大一个数。这意味着我们可以分解成子问题，每个扫描数组 [O(n)] 并且只关心它们各自的子数组。

代码

风格的解决方案（不要因为全局变量而评判我，我只是想让代码对非 C 语言的人可读）：

#include "stdio.h"

// Example problem:
const int array [] = {0, 7, 3, 1, 5};
const int N = 8; // size of original array
const int array_size = 5;

int SumOneTo (int n)
{
    return n*(n-1)/2; // non-inclusive
}

int MissingItems (const int begin, const int end, int & average)
{
    // We consider only sub-array elements with values, v:
    // begin <= v < end
    
    // Initialise info about missing elements.
    // First assume all are missing:
    int n = end - begin;
    int sum = SumOneTo(end) - SumOneTo(begin);

    // Minus everything that we see (ie not missing):
    for (int i = 0; i < array_size; ++i)
    {
        if ((begin <= array[i]) && (array[i] < end))
        {
            --n;
            sum -= array[i];
        }
    }
    
    // used by caller:
    average = sum/n;
    return n;
}

void Find (const int begin, const int end)
{
    int average;

    if (MissingItems(begin, end, average) == 1)
    {
        printf(" %d", average); // average(n) is same as n
        return;
    }
    
    Find(begin, average + 1); // at least one missing here
    Find(average + 1, end); // at least one here also
}

int main ()
{   
    printf("Missing items:");
    
    Find(0, N);
    
    printf("\n");
}

分析

暂时忽略递归，每个函数调用显然需要 O(n) 时间和 O(1) 空间。请注意，sum 可以等于 n(n-1)/2，因此需要存储 n-1 所需的双倍位数。最多这意味着我们实际上需要两个额外的元素空间，无论数组或 k 的大小如何，因此在正常约定下它仍然是 O(1) 空间。

对于 k 缺失的元素有多少函数调用并不那么明显，所以我将提供一个视觉效果。您的原始子数组（连接数组）是完整数组，其中包含所有 k 缺失元素。我们将按递增顺序想象它们，其中 -- 表示连接（同一子数组的一部分）：

m1 -- m2 -- m3 -- m4 -- (...) -- mk-1 -- mk

Find 函数的作用是将缺失的元素断开为不同的非重叠子数组。它保证每个子数组中至少有一个缺失元素，这意味着恰好断开一个连接。

这意味着无论拆分是如何发生的，它总是需要 k-1 Find 函数调用来完成查找其中只有一个缺失元素的子数组的工作。

所以时间复杂度是Θ((k-1 + k) * n) = Θ(k*n)。

对于空间复杂度，如果我们每次按比例划分，则得到 O(log(k)) 空间复杂度，但如果我们一次只分离一个，则得到 O(k)。

请参阅 here 以证明空间复杂度为何为 O(log(n))。鉴于上面我们已经证明它也是 O(k)，那么我们知道它是 O(min(k,log(n)))。

---

可能该算法适用于问题 1：

预先计算前 100 个整数的异或（val=1^2^3^4....100）异或元素，因为它们不断来自输入流（val1=val1^next_input）最终答案=val^val1

甚至更好：

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

这个算法实际上可以扩展为两个缺失的数字。第一步保持不变。当我们用两个缺失的数字调用 GetValue 时，结果将是 a1^a2 是两个缺失的数字。让我们说

val = a1^a2

现在要从 val 中筛选出 a1 和 a2，我们在 val 中获取任何设置位。假设 ith 位设置在 val 中。这意味着 a1 和 a2 在 ith 位位置具有不同的奇偶性。现在我们对原始数组进行另一次迭代并保留两个异或值。一个用于设置了第 i 位的数字，另一个用于未设置第 i 位的数字。我们现在有两个数字桶，它保证 a1 and a2 将位于不同的桶中。现在重复我们为在每个桶上查找一个缺失元素所做的相同操作。

---

你能检查每个数字是否存在吗？如果是，你可以试试这个：

S = 袋子中所有数字的总和 (S < 5050) Z = 缺失数字的总和 5050 - S

如果缺少的数字是 x 和 y，则：

x = Z - y 和 max(x) = Z - 1

因此，您检查从 1 到 max(x) 的范围并找到数字

---

有一种通用的方法可以泛化这样的流式算法。这个想法是使用一些随机化来希望将 k 元素“传播”到独立的子问题中，我们的原始算法可以为我们解决问题。该技术用于稀疏信号重建等。

制作一个大小为 u = k^2 的数组 a。

选择任何通用哈希函数 h : {1,...,n} -> {1,...,u}。 （如乘法移位）

对于 1, ..., n 中的每个 i，增加 a[h(i)] += i

对于输入流中的每个数字 x，递减 a[h(x)] -= x。

如果所有缺失的数字都被散列到不同的桶中，那么数组的非零元素现在将包含缺失的数字。

根据通用散列函数的定义，特定对被发送到同一个桶的概率小于 1/u。由于大约有 k^2/2 对，因此错误概率最多为 k^2/2/u=1/2。也就是说，我们成功的概率至少为 50%，如果我们增加 u，我们的机会就会增加。

请注意，该算法占用 k^2 logn 位空间（我们需要每个数组桶 logn 位。）这与@Dimitris Andreou 的答案所需的空间相匹配（特别是多项式分解的空间要求，它恰好也是随机的。 ) 该算法在每次更新时也有恒定的时间，而不是在幂和的情况下的时间 k。

事实上，通过使用评论中描述的技巧，我们甚至可以比幂和方法更有效。

---

如果您有两个列表的总和以及两个列表的乘积，则可以求解 Q2。

（l1 是原始列表，l2 是修改后的列表）

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

我们可以优化这一点，因为算术级数的总和是第一项和最后一项的平均值的 n 倍：

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

现在我们知道了（如果 a 和 b 是删除的数字）：

a + b = d
a * b = m

所以我们可以重新排列为：

a = s - b
b * (s - b) = m

并乘以：

-b^2 + s*b = m

并重新排列，使右侧为零：

-b^2 + s*b - m = 0

然后我们可以用二次公式求解：

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

示例 Python 3 代码：

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

我不知道 sqrt、reduce 和 sum 函数的复杂性，所以我无法计算出这个解决方案的复杂性（如果有人知道，请在下面评论。）

---

这是一个不依赖于 sdcvvc/Dimitris Andreou 的答案的复杂数学的解决方案，不会像 caf 和 Colonel Panic 那样更改输入数组，也不会像 Chris Lercher、JeremyP 和许多其他人做到了。基本上，我从 Svalorzen/Gilad Deutch 的 Q2 想法开始，将其推广到常见情况 Qk 并用 Java 实现以证明该算法有效。

这个想法

假设我们有一个任意区间 I，我们只知道它包含至少一个缺失的数字。在通过输入数组后，仅查看 I 中的数字，我们可以从 I 中获得总和 S 和缺失数字的数量 Q。我们只需在每次遇到 I 中的数字时减少 I 的长度即可（用于获得 Q）并通过每次将 I 中所有数字的预先计算的总和减去遇到的数字（用于获得 S）。

现在我们来看S和Q。如果Q=1，则表示I只包含一个缺失的数字，而这个数字显然是S。我们将I标记为已完成（在程序中称为“无歧义”）和将其排除在进一步考虑之外。另一方面，如果 Q > 1，我们可以计算 I 中包含的缺失数的平均 A = S / Q。由于所有数都是不同的，因此这些数中至少有一个严格小于 A，并且至少有一个严格小于大于 A。现在我们将 A 中的 I 分成两个较小的区间，每个区间至少包含一个缺失数。请注意，如果 A 是整数，我们分配哪个区间并不重要。

我们让下一个数组通过分别计算每个间隔的 S 和 Q（但在同一次通过），然后标记 Q = 1 的间隔和 Q > 1 的分割间隔。我们继续这个过程，直到没有新的“模棱两可的”区间，即我们没有什么可拆分的，因为每个区间都包含一个缺失的数字（我们总是知道这个数字，因为我们知道 S）。我们从包含所有可能数字的唯一“整个范围”区间开始（如问题中的 [1..N] ）。

时间和空间复杂度分析

在进程停止之前，我们需要进行的传递总数 p 永远不会大于丢失的数字计数 k。不等式 p <= k 可以严格证明。另一方面，还有一个经验上界 p < log2N + 3，对于较大的 k 值很有用。我们需要对输入数组的每个数字进行二分查找，以确定它所属的区间。这将 log k 乘数添加到时间复杂度中。

总的来说，时间复杂度为 O(N ᛫ min(k, log N) ᛫ log k)。请注意，对于较大的 k，这明显优于 sdcvvc/Dimitris Andreou 的方法，即 O(N ᛫ k)。

对于它的工作，该算法需要 O(k) 额外空间来存储最多 k 个间隔，这明显优于“bitset”解决方案中的 O(N)。

Java 实现

这是一个实现上述算法的 Java 类。它总是返回一个 排序 缺失数字数组。除此之外，它不需要丢失的数字计数 k，因为它在第一遍中计算它。整个数字范围由 minNumber 和 maxNumber 参数给出（例如，问题中的第一个示例为 1 和 100）。

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

为了公平起见，该类以 NumberBag 对象的形式接收输入。 NumberBag 不允许数组修改和随机访问，并且还会计算请求数组进行顺序遍历的次数。它也比 Iterable<Integer> 更适合大型数组测试，因为它避免了原始 int 值的装箱，并允许包装大型 int[] 的一部分以方便测试准备。如果需要，将 NumberBag 替换为 find 签名中的 int[] 或 Iterable<Integer> 类型并不难，方法是将其中的两个 for 循环更改为 foreach 循环。

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

测试

下面给出了演示这些类用法的简单示例。

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

可以通过这种方式执行大型阵列测试：

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Try them out on Ideone

---

我认为这可以在没有任何复杂的数学方程和理论的情况下完成。下面是一个就地和 O(2n) 时间复杂度解决方案的建议：

输入形式假设：

# 袋子里的数字 = n

# 缺失数字 = k

包中的数字由长度为 n 的数组表示

算法的输入数组长度 = n

数组中缺失的条目（从包中取出的数字）被数组中第一个元素的值替换。

例如。最初 bag 看起来像 [2,9,3,7,8,6,4,5,1,10]。如果取出 4，则 4 的值将变为 2（数组的第一个元素）。因此，取出 4 个后，袋子看起来像 [2,9,3,7,8,6,2,5,1,10]

此解决方案的关键是通过在遍历数组时否定该索引处的值来标记已访问数字的索引。

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

---

感谢这个非常有趣的问题：

因为你让我想起了牛顿的工作，它真的可以解决这个问题

请参考Newton's Identities

作为要查找的变量数 = 方程数（必须保持一致性）

我相信为此我们应该提高袋数的能力，以便创建许多不同的方程。

我不知道，但是，我相信是否应该有一个函数说 f 我们将为其添加 f( x_i )

x1 + x2 + ... + xk = z1

x12 + x22 + ... + xk2 = z2

…………

…………

…………

x1k + x2k + ... + xkk = zk

休息是一项不确定时间和空间复杂性的数学工作，但牛顿恒等式肯定会发挥重要作用。

我们不能使用集合论 .difference_update() 还是在这个问题方法中有线性代数的机会吗？

---

您可能需要澄清 O(k) 的含义。

这是任意 k 的简单解决方案：对于您的一组数字中的每个 v，累积 2^v 的总和。最后，将 i 从 1 循环到 N。如果 sum 按位与 2^i 相与为零，则 i 丢失。 （或者在数字上，如果总和除以 2^i 的下限是偶数。或者 sum modulo 2^(i+1)) < 2^i。）

容易，对吧？ O(N)时间，O(1)存储，支持任意k。

除了您要计算的大量数字在真实计算机上每个都需要 O(N) 空间。事实上，这个解决方案与位向量相同。

所以你可以很聪明地计算平方和和立方和......直到 v^k 的总和，然后做一些花哨的数学来提取结果。但这些也是很大的数字，这就引出了一个问题：我们在谈论什么抽象的操作模型？多少适合 O(1) 空间，需要多长时间来总结您需要的任何大小的数字？

---

我已经阅读了所有 30 个答案，并找到了最简单的答案，即使用 100 的位数组是最好的。但正如问题所说，我们不能使用大小为 N 的数组，我会使用 O(1) 空间复杂度和 k 次迭代，即 O(NK) 时间复杂度来解决这个问题。

为了使解释更简单，考虑到我得到了从 1 到 15 的数字，其中两个丢失了，即 9 和 14，但我不知道。让包看起来像这样：

[8,1,2,12,4,7,5,10,11,13,15,3,6]。

我们知道每个数字在内部都以位的形式表示。对于直到 16 的数字，我们只需要 4 位。对于 10^9 之前的数字，我们需要 32 位。但是让我们专注于 4 位，然后我们可以概括它。

现在，假设我们有从 1 到 15 的所有数字，那么在内部，我们将有这样的数字（如果我们对它们进行排序）：

0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

但是现在我们缺少两个数字。所以我们的表示看起来像这样（显示顺序是为了便于理解，但可以是任何顺序）：

(2MSD|2LSD)
00|01
00|10
00|11
-----
01|00
01|01
01|10
01|11
-----
10|00
missing=(10|01) 
10|10
10|11
-----
11|00
11|01
missing=(11|10)
11|11

现在让我们创建一个大小为 2 的位数组，其中包含具有相应 2 个最高有效位的数字的计数。 IE

= [__,__,__,__] 
   00,01,10,11

从左右扫描袋子并填充上面的数组，使得位数组的每个 bin 都包含数字的计数。结果如下：

= [ 3, 4, 3, 3] 
   00,01,10,11

如果所有的数字都存在，它会是这样的：

= [ 3, 4, 4, 4] 
   00,01,10,11

因此我们知道有两个数字丢失：一个最高 2 位有效数字为 10，另一个最高 2 位有效位为 11。现在再次扫描列表并为低 2 位有效数字填写一个大小为 2 的位数组。这一次，只考虑最高 2 位有效数字为 10 的元素。我们将位数组为：

= [ 1, 0, 1, 1] 
   00,01,10,11

如果所有数量的 MSD=10 都存在，我们将在所有箱中都有 1，但现在我们看到缺少一个。因此，我们有 MSD=10 和 LSD=01 缺失的数字，即 1001，即 9。

同样，如果我们再次扫描但只考虑 MSD=11 的元素，我们会得到 MSD=11 和 LSD=10 缺失，即 1110 即 14。

= [ 1, 0, 1, 1] 
   00,01,10,11

因此，我们可以在恒定的空间中找到缺失的数字。我们可以将其概括为 100、1000 或 10^9 或任何一组数字。

参考：http://users.ece.utexas.edu/~adnan/afi-samples-new.pdf 中的问题 1.6

---

非常好的问题。我会为 Qk 使用一组差异。许多编程语言甚至都支持它，比如在 Ruby 中：

missing = (1..100).to_a - bag

这可能不是最有效的解决方案，但如果我在这种情况下面临这样的任务（已知边界，低边界），我会在现实生活中使用它。如果数字集非常大，那么我当然会考虑更有效的算法，但在那之前，简单的解决方案对我来说就足够了。

---

您可以尝试使用 Bloom Filter。将袋子中的每个数字插入绽放中，然后遍历完整的 1-k 集，直到报告每个未找到。这可能无法在所有情况下都找到答案，但可能是一个足够好的解决方案。

---

我会对这个问题采取不同的方法，并询问面试官有关他试图解决的更大问题的更多细节。根据问题和围绕它的要求，明显的基于集合的解决方案可能是正确的，而后生成列表并通过它挑选的方法可能不是。

例如，面试官可能要发送 n 消息并且需要知道没有导致回复的 k，并且需要在 {3 之后尽可能短的挂钟时间知道它}th 回复到达。还可以说，消息通道的性质是，即使全速运行，也有足够的时间在消息之间进行一些处理，而不会影响在最后一个回复到达后产生最终结果所需的时间。这段时间可以用来将每个已发送消息的某些识别方面插入到一个集合中，并在每个相应的回复到达时将其删除。一旦最后一个回复到达，唯一要做的就是从集合中删除它的标识符，这在典型的实现中需要 O(log k+1)。之后，该集合包含 k 个缺失元素的列表，无需进行额外处理。

这当然不是批处理预先生成的数字包的最快方法，因为整个过程运行 O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k))。但它确实适用于 k 的任何值（即使它事先不知道），并且在上面的示例中，它以最小化最关键间隔的方式应用。

---

您可以通过从对称性（组，数学语言）的角度考虑解决方案来激发解决方案。无论这组数字的顺序如何，答案都应该是相同的。如果您打算使用 k 函数来帮助确定缺失的元素，您应该考虑哪些函数具有该属性：对称。函数 s_1(x) = x_1 + x_2 + ... + x_n 是对称函数的一个例子，但还有其他更高阶的例子。特别是考虑基本对称函数。 2 阶的初等对称函数是 s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n，即两个元素的所有乘积之和。对于 3 阶及更高阶的基本对称函数也是如此。它们显然是对称的。此外，事实证明它们是所有对称函数的构建块。

您可以通过注意 s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)) 来构建基本对称函数。进一步的思考应该会让你相信 s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) 等等，所以它们可以一次性计算出来。

我们如何判断数组中缺少哪些项目？考虑多项式 (z-x_1)(z-x_2)...(z-x_n)。如果您输入任何数字 x_i，它的计算结果为 0。展开多项式，得到 z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n。基本对称函数也出现在这里，这并不奇怪，因为如果我们对根应用任何置换，多项式应该保持不变。

所以我们可以建立多项式并尝试分解它以找出哪些数字不在集合中，正如其他人提到的那样。

最后，如果我们担心大量的内存溢出（第 n 个对称多项式的阶数为 100!），我们可以进行这些计算 mod p，其中 p 是大于 100 的素数。在这种情况下，我们计算多项式 mod p 并发现当输入是集合中的数字时它再次计算为 0，并且当输入不是集合中的数字时它计算为非零值。然而，正如其他人指出的那样，要及时从取决于 k 而不是 N 的多项式中获取值，我们必须对多项式 mod p 进行因式分解。

---

还有一种方法是使用残差图过滤。

假设我们有数字 1 到 4 并且缺少 3。二进制表示如下，

1 = 001b，2 = 010b，3 = 011b，4 = 100b

我可以创建一个如下所示的流程图。

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

请注意，流程图包含 x 个节点，而 x 是位数。最大边数为 (2*x)-2 。

因此，对于 32 位整数，它将占用 O(32) 空间或 O(1) 空间。

现在，如果我从 1、2、4 开始删除每个数字的容量，那么我会留下一个残差图。

0 ----------> 1 ---------> 1

最后，我将运行如下循环，

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

现在结果在 result 中也包含未丢失的数字（误报）。但是当有 k 个缺失元素时，k <=（结果的大小）<= n。

我将最后一次检查给定的列表以标记结果是否丢失。

所以时间复杂度将是 O(n) 。

最后，可以通过采用节点 00、01、11、10 而不仅仅是 0 和 1 来减少误报的数量（和所需的空间）。

---

我相信我有一个 O(k) 时间和 O(log(k)) 空间算法，因为您有用于任意大整数的 floor(x) 和 log2(x) 函数：

您有一个 k 位长整数（因此是 log8(k) 空格）在其中添加 x^2，其中 x 是您在包中找到的下一个数字：s=1^2+2^2+... 这需要 O(N) 时间（即对面试官来说不是问题）。最后，您会得到 j=floor(log2(s))，这是您要查找的最大数字。然后 s=s-j 并再次执行上述操作：

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

现在，您通常没有用于 2756 位整数的 floor 和 log2 函数，而是用于双精度数。所以？简单地说，对于每 2 个字节（或 1、3 或 4），您可以使用这些函数来获得所需的数字，但这会增加时间复杂度的 O(N) 因素

---

尝试找出从 1 到 50 的数字的乘积：

让产品，P1 = 1 x 2 x 3 x ............. 50

当你一个一个地取出数字时，将它们相乘，得到乘积 P2。但是这里缺少两个数字，因此 P2 < P1。

两个缺失项的乘积，axb = P1 - P2。

您已经知道总和，a + b = S1。

由上述两个方程，通过一个二次方程求解 a 和 b。 a 和 b 是您缺少的数字。

---