我有一段时间有一个有趣的面试经历。问题开始很简单：
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.
所以这里的问题很简单：
O(N)位。我们无法承受与N成比例的任何额外空间。所以，当然你必须扫描O(N)中的输入，但是你只能捕获少量信息（用k而不是N来定义），然后必须以某种方式找到k个缺失的数字。
以下是Dimitris Andreou's link的摘要。
记住i次幂的总和，其中i = 1,2，...，k。这减少了求解方程组的问题
a1 + a2 + ... +和+ b1
A + 12 +障碍+ ... + Acre = Ba
...
A + C +障碍+ ... + A + b
使用Newton's identities，知道bi允许计算
c1 = a1 + a2 + ...和
c2 = a1a2 + a1a3 + ... +和-1ak
...
ck = a1a2 ...和
如果展开多项式（x-a1）...（x-ak），系数将精确为c1，...，ck - 请参阅Viète's formulas。由于每个多项式因子唯一（多项式环是Euclidean domain），这意味着ai是唯一确定的，直到排列。
这结束了一个证据，即记住功率足以恢复数字。对于常数k，这是一个很好的方法。
然而，当k变化时，计算c1，...，ck的直接方法是非常昂贵的，因为例如ck是所有缺失数字的乘积，幅度为n！/（n-k）！为了克服这一点，执行computations in Zq field，其中q是素数，使得n <= q <2n - 它由Bertrand's postulate存在。证明不需要改变，因为公式仍然成立，并且多项式的因子分解仍然是唯一的。您还需要一种用于有限域分解的算法，例如Berlekamp或Cantor-Zassenhaus的算法。
常数k的高级伪代码：
对于变化的k，使用例如，找到素数n <= q <2n。米勒 - 拉宾，并执行所有数字减少modulo q的步骤。
编辑：此答案的先前版本指出，在q为素数的情况下，代替Zq，可以使用特征2的有限域（q = 2 ^（log n））。情况并非如此，因为牛顿的公式需要按数字除以k。
要解决2（和3）缺失数字问题，您可以修改quickselect，它平均在O(n)中运行，并且如果分区就地完成则使用常量内存。
p的集合划分为分区l（包含小于枢轴的数字）和r（包含大于枢轴的数字）。p - 1 - count(l) = count of missing numbers in l和n - count(r) - p = count of missing numbers in r）进行比较，确定2个缺失数字所在的分区(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);
}
}
这是一个使用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; }
}
}
你能检查一下这个号码是否存在吗？如果是，您可以尝试这样做：
S =袋中所有数字的总和（S <5050） Z =缺失数字5050-S的总和
如果缺少的数字是x和y那么：
x = Z - y和 max（x）= Z - 1
因此，你可以检查从1到max(x)的范围，找到该数字
也许这个算法可以用于问题1：
甚至更好：
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位位置具有不同的奇偶校验。现在我们在原始数组上进行另一次迭代并保留两个xor值。一个用于具有第i位设置的数字，另一个用于没有第i位设置的数字。我们现在有两个数字桶，并保证a1 and a2将在不同的桶中。现在重复我们在每个桶上找到一个缺少元素所做的相同操作。
如果您有两个列表的总和和两个列表的乘积，您可以解决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函数的复杂性，所以我无法弄清楚这个解决方案的复杂性（如果有人知道请在下面评论。）
对于Q2，这是一个比其他解决方案效率低一点的解决方案，但仍然具有O（N）运行时并且需要O（k）空间。
想法是运行原始算法两次。在第一个中，您会得到一个缺失的总数，它会为您提供缺失数字的上限。我们把这个号码称为N。你知道丢失的两个数字将总结为N，所以第一个数字只能在[1, floor((N-1)/2)]区间，而第二个数字将在[floor(N/2)+1,N-1]。
因此，您再次循环所有数字，丢弃第一个间隔中未包含的所有数字。那些是，你跟踪他们的总和。最后，你会知道丢失的两个数字中的一个，并且扩展第二个。
我有一种感觉，这种方法可以推广，也许多次搜索在输入的单次传递中以“并行”方式运行，但我还没弄清楚如何。
我认为这可以在没有任何复杂的数学方程和理论的情况下完成。以下是针对现有和O（2n）时间复杂度解决方案的提议：
输入形式假设：
bag中的数字数量= n
丢失的数字数= k
袋子中的数字由长度为n的数组表示
算法的输入数组的长度= n
数组中缺少的条目（从包中取出的数字）将替换为数组中第一个元素的值。
例如。最初的包看起来像[2,9,3,7,8,6,4,5,1,10]。如果取出4，则值4将变为2（数组的第一个元素）。因此在拿出4个包之后会看起来像[2,9,3,7,8,6,2,5,1,10]
此解决方案的关键是通过在遍历数组时取消该INDEX处的值来标记访问数字的INDEX。
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;
}
有一种通用的方法来推广像这样的流式算法。我们的想法是使用一些随机化来有希望地将k元素“扩散”到独立的子问题中，我们的原始算法为我们解决了问题。该技术用于稀疏信号重建等。
a大小的u = k^2阵列。h : {1,...,n} -> {1,...,u}。 （像multiply-shift）i中的每个1, ..., n增加a[h(i)] += ix，递减a[h(x)] -= x。如果所有丢失的数字都被散列到不同的桶，则数组的非零元素现在将包含缺失的数字。
通过定义通用散列函数，将特定对发送到同一桶的概率小于1/u。由于有大约k^2/2对，我们有错误概率最多k^2/2/u=1/2。也就是说，我们成功的概率至少为50％，如果我们增加u，我们就会增加机会。
请注意，此算法需要k^2 logn位空间（我们需要每个阵列桶使用logn位。）这匹配@Dimitris Andreou的答案所需的空间（特别是多项式因子分解的空间要求，也恰好是随机化的。）此算法也每次更新都有恒定的时间，而不是在功率和的情况下时间k。
实际上，通过使用注释中描述的技巧，我们可以比功率和方法更有效。
您可能需要澄清O（k）的含义。
这是任意k的一个简单解决方案：对于你的数字集合中的每个v，累加2 ^ v的总和。最后，循环i从1到N.如果与2 ^ i按位和，则为零，则i丢失。 （或数字上，如果总和除以2 ^ i的平均值是偶数。或者sum modulo 2^(i+1)) < 2^i。）
容易，对吗？ O（N）时间，O（1）存储，并且它支持任意k。
除了你计算在真实计算机上需要O（N）空间的大量数字。实际上，这个解决方案与位向量相同。
因此，您可以聪明地计算平方和平方和和平方和的总和......直到v ^ k的总和，并进行花式数学提取结果。但这些也是大数字，这引出了一个问题：我们在谈论什么样的抽象运作模式？在O（1）空间中适合多少，以及总结所需数量的数量需要多长时间？
非常好的问题。我会为Qk使用一组差异。许多编程语言甚至都支持它，比如Ruby：
missing = (1..100).to_a - bag
它可能不是最有效的解决方案，但如果我在这种情况下遇到这样的任务（已知的边界，低边界），它将是我在现实生活中使用的解决方案。如果数字的集合非常大，那么我会考虑一种更有效的算法，但在此之前，简单的解决方案对我来说已经足够了。
你可以通过阅读几页Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers找到它。它显示了您正在寻找的概括。这可能是你的面试官阅读的内容以及他提出这些问题的原因。
现在，如果只有人们会开始删除被Muthukrishnan治疗所包含或取代的答案，并使这个文本更容易找到。 :)
另请参阅sdcvvc's直接相关的答案，其中还包括伪代码（欢呼！不需要阅读那些棘手的数学公式:)）（谢谢，干得好！）。
你可以尝试使用Bloom Filter。将包中的每个数字插入到bloom中，然后遍历完整的1-k集，直到报告每个未找到的数字。这可能无法在所有情况下找到答案，但可能是一个足够好的解决方案。
我会对这个问题采取不同的方法，并向访调员探讨他正试图解决的更大问题的更多细节。根据问题及其周围的要求，明显的基于集合的解决方案可能是正确的，并且生成列表和后续选择方法可能不是。
例如，可能是面试官要发送n消息，并且需要知道没有得到回复的k，并且需要在n-kth回复到达后尽可能少的挂钟时间知道它。我们还要说消息通道的本质是即使在全口径运行，也有足够的时间在消息之间进行一些处理，而不会影响在最后一个回复到达后产生最终结果所需的时间。该时间可以用于将每个发送的消息的一些识别方面插入到集合中并在每个相应的答复到达时将其删除。一旦最后一个回复到达，唯一要做的就是从集合中删除它的标识符，在典型的实现中需要使用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)。如果你输入任何数字0，它会评估为x_i。扩展多项式，得到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-bit整数的floor和log2函数，而是双精度函数。所以？简单地说，对于每2个字节（或1个，3个或4个），您可以使用这些函数来获得所需的数字，但这会增加时间复杂度的O(N)因子
这可能听起来很愚蠢，但是，在呈现给您的第一个问题中，您必须看到包中的所有剩余数字实际添加它们以使用该等式找到丢失的数字。
因此，既然您可以查看所有数字，只需查找缺少的数字。当两个数字丢失时也是如此。我觉得很简单。当你看到袋子里剩下的数字时，使用方程是没有意义的。
我认为这可以概括为：
将S，M表示为算术级数和乘法之和的初始值。
S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n
我应该考虑计算这个的公式，但这不是重点。无论如何，如果缺少一个数字，您已经提供了解决方案。但是，如果缺少两个数字，那么让我们用S1和M1表示新的总数和总数，如下所示：
S1 = S - (a + b)....................(1)
Where a and b are the missing numbers.
M1 = M - (a * b)....................(2)
既然你知道了S1，M1，M和S，那么上面的等式就可以找到a和b，即缺失的数字。
现在缺少三个数字：
S2 = S - ( a + b + c)....................(1)
Where a and b are the missing numbers.
M2 = M - (a * b * c)....................(2)
现在你的未知数是3，而你只有两个可以解决的方程式。
我不知道这是否有效，但我想建议这个解决方案。
现在运行一个循环来获得可能的对（p，q），它们都位于[1,100]并且总和为d。
当获得一对时，检查是否（3的结果）XOR p = q并且如果是，我们完成了。
如果我错了，请纠正我，如果这是正确的，还要评论时间复杂性
我们可以在大多数情况下在O（log n）中执行Q1和Q2。
假设我们的memory chip由n数量的test tubes组成。试管中的数字x由化学液体的x milliliter表示。
假设我们的处理器是laser light。当我们点亮激光时，它会垂直穿过所有管子的长度。每当它通过化学液体时，发光度就会被1降低。并且以一定毫升的标记传递光是O(1)的操作。
现在，如果我们将激光照射在试管中间并获得光度输出
n/2。n/2。我们还可以检查1或2是否降低了光度。如果它被1减少，那么一个缺失的数字小于n/2而其他数字大于n/2。如果它被2减少，则两个数字都小于n/2。我们可以一次又一次地重复上述过程，缩小我们的问题域。在每一步中，我们将域缩小一半。最后我们可以得到我们的结果。
值得一提的并行算法（因为它们很有趣），
O(log^3 n)时间完成。然后可以通过O(log n)时间的二进制搜索找到丢失的数字。n处理器，那么每个进程都可以检查其中一个输入并设置一些标识数字的标志（方便地在数组中）。在下一步中，每个进程都可以检查每个标志，最后输出未标记的数字。整个过程将需要O(1)时间。它有额外的O(n)空间/内存要求。请注意，上面提供的两个并行算法可能需要额外的空间，如注释中所述。
可能的解决方案：
public class MissingNumber {
public static void main(String[] args) {
// 0-20
int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
printMissingNumbers(a,20);
}
public static void printMissingNumbers(int [] a, int upperLimit){
int b [] = new int[upperLimit];
for(int i = 0; i < a.length; i++){
b[a[i]] = 1;
}
for(int k = 0; k < upperLimit; k++){
if(b[k] == 0)
System.out.println(k);
}
}
}
我们可以通过将数字本身和数字的平方相加来求解Q2。
然后我们可以将问题减少到
k1 + k2 = x
k1^2 + k2^2 = y
其中x和y的总和低于预期值。
替代给了我们：
(x-k2)^2 + k2^2 = y
然后我们可以解决以确定我们缺少的数字。
尝试找到1到50之间的数字乘积：
设产品，P1 = 1 x 2 x 3 x ............. 50
当您逐个取出数字时，将它们相乘以便得到产品P2。但这里缺少两个数字，因此P2 <P1。
两个mising项的乘积，a x b = P1 - P2。
你已经知道了总和，a + b = S1。
从上述两个方程中，通过二次方程求解a和b。 a和b是你缺少的号码。
正如@j_random_hacker指出的那样，这与Finding duplicates in O(n) time and O(1) space非常相似，我的答案也适用于此。
假设“bag”由大小为A[]的基于1的数组N - k表示，我们可以在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)时间运行 - 只有i这样A[i] != i才会发生交换，并且每个交换设置至少一个元素，使得A[i] == i，之前不是真的。这意味着交换的总数（以及因此while循环体的执行总数）最多为N-1。
第三个循环打印那些未被值i占用的数组i的索引 - 这意味着i必定已经丢失。
我问一个4岁的孩子来解决这个问题。他对数字进行了排序，然后计算在内。这有一个空间要求O（厨房地板），它的工作同样容易，但很多球丢失。
不确定，如果它是最有效的解决方案，但我会遍历所有条目，并使用bitset记住，设置哪些数字，然后测试0位。
我喜欢简单的解决方案 - 我甚至相信，它可能比计算总和或平方和等更快。
我没有检查数学，但我怀疑在计算Σ(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的列表中。