简单的面试问题变得更难：给定数字1…100，找到缺失的数字，正好给出k是缺失的

我们可以通过对数字本身和数字的广场求和来求解Q2。

我们可以将问题简化为

k1 + k2 = xk1^2 + k2^2 = y

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

替换给我们：

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

然后我们可以解决这个问题来确定我们缺失的数字。

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

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

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

x=Z-y和
max（x）=Z-1

所以你检查从1到max(x)的范围并找到数字

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

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

我还没有检查数学，但我怀疑在计算Σ(n)的同一过程中计算Σ(n^2)将提供足够的信息来获得两个缺失的数字，如果有三个，也做Σ(n^3)，依此类推。

对于k的不同值，方法会不同，因此不会有关于k的通用答案。例如，对于k=1，可以利用自然数的和，但对于k=n/2，必须使用某种位集。对于k=n-1，同样的方法，可以简单地将袋子中唯一的数字与其他数字进行比较。

非常好的问题。我会为Qk使用设置差异。很多编程语言甚至都支持它，比如Ruby：

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

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

等一下。正如问题所述，袋子里有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的列表中。

你会通过阅读Muthukrishnan-数据流算法：谜题1：查找丢失的数字.它准确地显示了您正在寻找的泛化的几页找到它。也许这就是你的面试官读到的以及他提出这些问题的原因。

另见sdcvvc的直接相关答案，其中还包括伪代码（万岁！不需要阅读那些棘手的数学公式：））（谢谢，很棒的工作！）。

这是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_我允许计算

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公式。由于每个多项式因子都是唯一的（多项式环是欧几里德域），这意味着_我是唯一确定的，直到排列。

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

然而，当k变化时，计算c₁，…， c_k的直接方法非常昂贵，因为例如c_k是所有缺失数的乘积，大小为n！/（n-k）！。为了克服这一点，执行Z_q字段中的计算，其中q是素数，使得n<=q<2n-它存在于伯特兰的假设。证明不需要改变，因为公式仍然成立，多项式的因式分解仍然是唯一的。你还需要一个有限域上的因式分解算法，例如Berlekamp或Cantor-Zassenhaus。

常量k的高级伪代码：

• 计算给定数字的i次幂
• 减去得到未知数的第i次幂的和。称其为总和b_我。
• 使用牛顿恒等式从b_我计算系数；称之为c_我。基本上，c₁=b₁；c₂=（c₁b₁-b₂）/2；有关确切公式，请参阅维基百科

基于数字和的解决方案的问题是，它们没有考虑存储和处理具有大指数的数字的成本……在实践中，为了使其适用于非常大的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) + 1l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1l_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) + 1t < 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 =letmid = (low + high) `div` 2klow = countInRange low midkhigh = krange - klowinfindMissing (findMissing low mid klow) (mid + 1) high khighinfindMising 1 (n - k) k

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

你可以尝试使用布隆过滤器。将包中的每个数字插入到布隆中，然后迭代完整的1-k集，直到报告每个未找到。这可能不会在所有情况下找到答案，但可能是一个足够好的解决方案。

对于这个问题，我会采取不同的方法，并向面试官询问他试图解决的更大问题的更多细节。根据问题及其周围的要求，显而易见的基于集合的解决方案可能是正确的，而生成列表并随后选择它的方法可能不是。

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

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

我相信我有一个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位整数的地板和log2函数，而是用于双精度。那么？简单地说，对于每2个字节（或1、3或4），您可以使用这些函数来获取所需的数字，但这会增加时间复杂度的O(N)因素

正如@j_random_hacker所指出的，这与在O（n）时间和O（1）空间中查找重复非常相似，我的答案的改编在这里也有效。

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

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

for i := n - k + 1 to nA[i] := A[1]end for
for i := 1 to n - kwhile A[A[i]] != A[i]swap(A[i], A[A[i]])end whileend for
for i := 1 to nif A[i] != i thenprint iend ifend for

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

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

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

第三个循环打印数组i中没有被值i占用的索引——这意味着i一定丢失了。

也许这个算法可以解决问题1：

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

或者更好：

def GetValue(A)val=0for i=1 to 100doval=val^idonefor value in A:doval=val^valuedonereturn val

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

val = a1^a2

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

如果一个数字只出现一次，很容易通过以下方式判断：

创建一个布尔数组boolArray，大小为给定数字；这里是100。

遍历输入数字并根据数字值将元素设置为true。例如，如果找到45，则设置boolArray[45-1] = true；

这将是一个O（N）操作。

然后循环遍历boolArray。如果一个元素保持假，那么元素+1的索引就是缺失的数字。例如，如果boolArray[44]为假，我们知道45号缺失。

这是一个O（n）操作。空间复杂度是O（1）。

所以这个解决方案可以从给定的连续数集中找到任何缺失的数字。

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

输入形式假设：

#包中的数字=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]

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

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers){List<int> missingNumbers = new List<int>();int arrayLength = arrayOfNumbers.Length;
//First Passfor (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 numbersfor (int i = 0; i < arrayLength; i++){//If this index is unvisited, means this is a missing numberif (arrayOfNumbers[i] > 0){missingNumbers.Add(i + 1);}}
return missingNumbers;}

我们可以使用以下简单的代码来查找重复值和缺失值：

    int size = 8;int arr[] = {1, 2, 3, 5, 1, 3};int result[] = new int[size];
for(int i =0; i < arr.length; i++){if(result[arr[i]-1] == 1){System.out.println("repeating: " + (arr[i]));}result[arr[i]-1]++;}
for(int i =0; i < result.length; i++){if(result[i] == 0){System.out.println("missing: " + (i+1));}}

我请一个4岁的孩子来解决这个问题。他把数字排序，然后一起数。这需要O（厨房地板）的空间，不管少了多少球，它都一样容易。

一个可能的解决方案：

public class MissingNumber {public static void main(String[] args) {// 0-20int [] 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);}}}

// Size of numbersdef n=100;
// A list of numbers that is missing k numbers.def list;
// A mapdef map = [:];
// Populate the map so that it contains all numbers.for(int index=0; index<n; index++){map[index+1] = index+1;}
// Get size of list that is missing k numbers.def size = list.size();
// Remove all numbers, that exists in list, from the map.for(int index=0; index<size; index++){map.remove(list.get(index));}
// Content of map is missing numbersprintln("Missing numbers: " + map);

假设它是一个从1到N的数组，其元素为a1， a2，…， aN：

1+N=N+1;2+N-1=N+1;

…所以这里的和是唯一的。我们可以从开始和结束扫描数组以添加两个元素。如果总和为N+1；然后好的，否则它们会丢失。

for (I <= N/2) {temp = a[I] + a[n-I];if (temp != N+1) thenFind the missing number or numbers}

重复这个循环，你很容易得到答案。

我认为这可以概括为：

表示S，M作为算术级数和乘法的初始值。

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2M = 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，而你只有两个方程可以解决。

这是一个使用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 presentfor (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 onesfor (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; }}}

这是一个很简单的问题

void findMissing(){bool record[N] = {0};for(int i = 0; i < N; i++){record[bag[i]-1] = 1;}for(int i = 0; i < N; i++){if(!record[i]) cout << i+1 << endl;}}

O（n）时间复杂度和空间复杂度

我不知道这是否有效，但我想建议这个解决方案。

1. 计算100个元素的异或
2. 计算98个元素的异或（删除2个元素后）
3. 现在（1的结果）XOR（2的结果）给出两个缺失的数字i… e a XOR b的异或，如果a和b是缺失的元素
   4.用你通常的求和公式diff得到缺失的Nos的总和，假设diff是d。

现在运行一个循环来获取可能的对（p， q），它们都位于[1,100]和sum到d。

当获得一对时，检查（3的结果）XOR p=q如果是，我们就完成了。

如果我错了，请纠正我，如果这是正确的，请评论时间复杂度

如果你有两个列表的总和和两个列表的乘积，你可以求解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 = da * b = m

所以我们可以重新安排：

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

然后乘以：

-b^2 + s*b = m

然后重新排列，使右侧为零：

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

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

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

示例Python 3代码：

from functools import reduceimport operatorimport mathx = 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))))/-2a = s - bprint(a,b) #15,5

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

关键是使用索引来标记范围内是否存在数字。这里我们知道我们有1到N。时间复杂度O（n）空间复杂度O（1）

后续提问：这可以被修改以查找差异d的AP中是否缺少元素。其他变化可能包括从任何包含-ve数的随机数组中查找第一个丢失的+ve数。然后首先分区围绕0快速排序，然后在分区右侧的一部分 数组上执行此过程，进行必要的修改。

public static void  missing(int [] arr){for(int i=0; i< arr.length; i++){if(arr[i]!=-1 && arr[i]<=arr.length){int idx=i;while(idx>=0 && idx<arr.length&& arr[idx]!=-1 ){int temp =arr[idx];// temp-1 because array index starts from 0, i.e a[0]=-1 is indicates that 1 is present in the arrayarr[temp-1]=-1;idx=temp-1;}}}}

在此之后，我们需要迭代数组，并检查是否a[i]！=-1，那么i+1是缺失的数字。当a[i]>N时，我们必须小心。

你可以通过考虑对称（数学语言中的群）来激励解决方案。无论数字集的顺序如何，答案都应该是相同的。如果你要使用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。

    //sortint missingNum[2];//missing 2 numbers- can be applied to more than 2int j = 0;for(int i = 0; i < length - 1; i++){if(arr[i+1] - arr[i] > 1 ) {missingNum[j] = arr[i] + 1;j++;}}

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

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

2. 通过将数据透视值与每个分区的大小（p - 1 - count(l) = count of missing numbers in l和p - 1 - count(l) = count of missing numbers in l）进行比较，确定2个缺失数字所在的分区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 sumsprint array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";}else if(count($l) < $pivot - $min) {// more than 1 missing number, recursefindMissing($l, $min, $pivot-1);}
if(count($r) == $max - $pivot - 1) {// only 1 missing number use difference of sumsprint array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";} else if(count($r) < $max - $pivot) {// mroe than 1 missing number recursefindMissing($r, $pivot+1, $max);}}

演示

我使用Java8和Java8之前编写的代码。它使用公式：（N*（N+1））/2表示所有数字的总和。

import java.util.ArrayList;import java.util.Arrays;import java.util.List;
/***** @author pradeep**         Answer : SumOfAllNumbers-SumOfPresentNumbers=Missing Number;**         To GET SumOfAllNumbers : Get the highest number (N) by checking the*         length. and use the formula (N*(N+1))/2**         To GET SumOfPresentNumbers: iterate and add it***/public class FindMissingNumber {/*** Before Java 8** @param numbers* @return*/public static int missingNumber(List<Integer> numbers) {int sumOfPresentNumbers = 0;for (Integer integer : numbers) {sumOfPresentNumbers = sumOfPresentNumbers + integer;}int n = numbers.size();int sumOfAllNumbers = (n * (n + 1)) / 2;return sumOfAllNumbers - sumOfPresentNumbers;}/*** Using Java 8 . mapToInt & sum using streams.** @param numbers* @return*/public static int missingNumberJava8(List<Integer> numbers) {int sumOfPresentNumbers = numbers.stream().mapToInt(i -> i).sum();int n = numbers.size();int sumOfAllNumbers = (n * (n + 1)) / 2;return sumOfAllNumbers - sumOfPresentNumbers;}public static void main(String[] args) {List<Integer> list = new ArrayList<>();list = Arrays.asList(0, 1, 2, 4);System.out.println("Missing number is :  " + missingNumber(list));System.out.println("Missing number using Java 8 is : " + missingNumberJava8(list));}}*

有一种通用的方法可以解决这样的流问题。这个想法是使用一些随机化，希望将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，这是一个比其他解决方案更低效的解决方案，但仍然有O（N）运行时并占用O（k）空间。

这个想法是运行原始算法两次。在第一个中，你得到一个缺失的总数，这给了你缺失数字的上界。让我们称这个数字为N。你知道缺失的两个数字将总和为N，所以第一个数字只能在区间[1, floor((N-1)/2)]中，而第二个数字将在[floor(N/2)+1,N-1]中。

因此，您再次循环所有数字，丢弃所有未包含在第一个间隔中的数字。那些是，您跟踪它们的总和。最后，您将知道缺少的两个数字中的一个，并通过扩展知道第二个。

我有一种感觉，这种方法可以推广，也许在一次传递输入期间，多个搜索以“并行”的方式运行，但我还没有弄清楚如何。

您可能需要澄清O（k）的含义。

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

很简单，对吧？O（N）时间，O（1）存储，它支持任意k。

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

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

您可以使用二进制搜索来查找缺失（或连续）数字的间隔。运行时间应该在（num间隔）*log（avg间隔长度）*N左右。如果间隔不多，则很有用。

一种方法是计算素数101的模。

计算并存储整数1到100的乘积，将此数取模101。小exo：结果将是1。

计算并存储所有数字1到100的总和，将结果模101化简。小exo：结果将为0。

现在假设袋子中删除了数字x和y。

计算乘积和总和的一切在袋模101。所以我将知道的值

a=x+y和b=x*y

模101。

现在很容易找到x和y模101（在具有101个元素的有限域上求解二次多边形）。

现在你知道x和y模101，但由于你也知道x和y小于101，你知道它们的真实值。

免责声明：我已经阅读这个问题好几天了，但它超出了我的知识范围，无法理解数学。

我尝试使用set来解决它：

arr=[1,2,4,5,7,8,10] # missing 3,6,9NMissing=3arr_origin = list(range(1,arr[-1]+1))
for i in range(NMissing):arr.append(arr[-1]) ##### assuming you do not delete the last one
arr=set(arr)arr_origin=set(arr_origin)missing=arr_origin-arr # 3 6 9

我们大部分时间都可以在O（log n）中做q1和q2。

假设我们的memory chip由test tubes的n数组组成。试管中的数字x由化学液体的xmilliliter表示。

假设我们的处理器是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)空间/内存要求。

注意，上面提供的两个并行算法可能需要额外的空间，如注释中所述。

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

假设我们有数字1到4,3不见了。二进制表示如下，

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

我可以创建如下的流程图。

                   11 -------------> 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来减少误报的数量（以及所需的空间）。

假设一个ArrayList对象（myList）被这些数字填充，其中缺少2个数字x和y。所以可能的解决方案可以是：

int k = 1;while (k < 100) {if (!myList.contains(k)) {System.out.println("Missing No:" + k);}k++;}

您还可以创建大小为last_element_in_the_existing_array + 1的布尔数组。

在for循环中，标记现有数组中存在的所有元素true。

在另一个for循环中打印包含false AKA缺失元素的元素的索引。

时间复杂度：O(last_element_in_the_existing_array)

空间复杂度：O(array.length)

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

这是一个解决方案，它不像sdcvvc/Dimitris Andreou的答案那样依赖复杂的数学，不像caf和Panic上校那样改变输入数组，也不像Chris Lercher、JermyP和许多其他人那样使用巨大的位集。基本上，我从Svalorzen/Gilad Deutch对Q2的想法开始，将其推广到普通情况Qk，并在Java实现以证明算法有效。

这个想法

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

现在我们看一下S和Q。如果q=1，意味着我只包含其中一个缺失的数字，这个数字显然是S。我们将我标记为完成（在程序中称为“无歧义”），不再进一步考虑。另一方面，如果Q>1，我们可以计算我中包含的缺失数字的平均值A=S/Q。由于所有数字都是不同的，因此至少有一个这样的数字严格小于一个，至少有一个严格大于一个。现在我们将一个中的我分成两个较小的区间，每个区间至少包含一个缺失的数字。请注意，如果它是一个整数，我们分配一个的间隔并不重要。

我们进行下一次数组传递，分别计算每个区间的S和Q（但在同一次传递中），然后用q=1标记区间，用Q>1分割区间。我们继续这个过程，直到没有新的“模糊”区间，即我们没有什么可以分割的，因为每个区间只包含一个缺失的数字（我们总是知道这个数字，因为我们知道S）。我们从包含所有可能数字的唯一“全范围”区间开始（就像问题中的[1. N]）。

时间复杂度和空间复杂度分析

在进程停止之前，我们需要进行的p次遍历的总数永远不会大于缺失的数字计数k。不等式p<=k可以得到严格证明。另一方面，还有一个经验上界p2N+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 exclusivethis.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 identifieditv.ambiguous = false;elseintervalCount++; // 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 >= oldIndexInterval itv = intervals[oldIndex];int begin = itv.begin;if (itv.ambiguous) {// split interval itv// use floorDiv instead of / because input numbers can be negativeint mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;intervals[newIndex--] = new Interval(mean, end);intervals[newIndex--] = new Interval(begin, mean);} elseintervals[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 belongsint 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[]的一部分，以方便测试准备。如果需要，通过将find签名中的两个for循环更改为Foreach，不难将NumberBag替换为int[]或Iterable<Integer>类型。

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 intpublic 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 Eratosthenesfinal 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 primeint q = p;for (int i = lastPrimeIndex++; i < primes.length; i++) {q = primes[i]; // not necessarily primeint 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)) + 2return 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 testpublic int makeTest(int missingCount) {this.missingCount = missingCount;// numbers array is reused when numberCount stays the same,// just Fisher–Yates shuffle it for each testfor (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 numbersArrays.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);}}

在Ideone上试用它们

我已经阅读了所有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的所有数字，那么在内部，我们会有这样的数字（如果我们对它们进行排序）：

000100100011010001010110011110001001101010111100110111101111

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

(2MSD|2LSD)00|0100|1000|11-----01|0001|0101|1001|11-----10|00missing=(10|01)10|1010|11-----11|0011|01missing=(11|10)11|11

现在让我们制作一个大小为2的位数组，用于保存具有相应的2个最高有效数字的数字计数。即

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

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

= [ 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或任何一组数字。

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

动机

如果你想解决一般情况下的问题，并且你可以存储和编辑数组，那么Caf的解决方案是迄今为止最有效的。如果你不能存储数组（流式版本），那么sdcvvc的回答是目前建议的唯一解决方案。

如果你可以存储数组但不能编辑它，我提出的解决方案是最有效的答案（到目前为止在这个线程上），我从Svalorzen溶液那里得到了这个想法，它解决了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风格的解决方案（不要因为全局变量而评判我，我只是想让代码对非c语言的人来说是可读的）：

#include "stdio.h"
// Example problem:const int array [] = {0, 7, 3, 1, 5};const int N = 8; // size of original arrayconst 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 nreturn;}    
Find(begin, average + 1); // at least one missing hereFind(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个缺失的元素。我们将以递增的顺序想象它们，其中--表示连接（同一子数组的一部分）：

m₁--m₂--m₃--m₄--（…）--m_k-1--m_k

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

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

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

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

关于为什么空间复杂度为O(log(n))的证明，请参见这里。鉴于上面我们已经证明它也是O(k)，那么我们知道它是O(min(k,log(n)))。

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

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

请参阅牛顿恒等式

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

我相信为此，我们应该提高对包数的功率，以便创建许多不同的方程。

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

x₁+x₂+…+x_k=z₁

x₁²+x₂²+…+x_k²=z₂

……

……

……

x₁^k+x₂^k+…+x_k^k=z_k

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

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