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

我们可以通过对数字本身和数字的平方求和来解决 Q2。

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

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

总和低于预期值的位置和距离。xy

代入为我们提供了：

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

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

你能检查每个数字是否存在吗？如果是，您可以尝试以下操作：

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

如果缺少的数字是 ，则：xy

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

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

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

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

我没有检查过数学，但我怀疑在我们计算的同一阶段进行计算会提供足够的信息来获得两个缺失的数字，如果有三个数字，也要这样做，依此类推。Σ(n^2)Σ(n)Σ(n^3)

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

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

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

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

等一会。正如问题所说，袋子里有 100 个数字。无论 k 有多大，问题都可以在恒定时间内解决，因为您可以在循环的最多 100 次迭代中使用集合并从集合中删除数字。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 - Data Stream Algorithms： Puzzle 1： Finding Missing Numbers 的几页找到它。它准确地显示了您正在寻找的泛化。可能这就是你的面试官读到的内容，以及他提出这些问题的原因。

---

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

以下是迪米特里斯·安德烈欧（Dimitris Andreou）链接的摘要。

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

一个₁ + 一个₂ + ... + 一个_k = b₁

一个₁² + 一个₂ 2 + ... + 一个_k 2 = b ²

...

一个₁ k +_{一个 2} k + ... + a k k = b _k

使用牛顿恒等式，知道 b_i 可以计算

c 1 = 一个₁ +_{一个 2} + ...一个_k

c 2 = 一个 1 一个₂ + 一个₁一个₃ + ... + 一个_k-1一个_k

...

c_k =_{一个 1}一个₂ ...一个_k

如果展开多项式 （x-a₁）...（x-a k） 系数将正好是 c₁， ...， c_k - 参见 Viète 公式。由于每个多项式因子都是唯一的（多项式环是一个欧几里得域），这意味着_i 是唯一确定的，直到排列。

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

然而，当 k 发生变化时，计算 c₁,...,c k 的直接方法非常昂贵，因为例如 c k 是所有缺失数的乘积，量级为 n！/（_n-k）！。为了克服这个问题，在 Z q 字段中进行计算，其中 q 是一个素数，使得 n <= q < 2n - 它存在于 Bertrand 假设中。证明不需要改变，因为公式仍然成立，多项式的因式分解仍然是唯一的。您还需要一种用于有限域因式分解的算法，例如 Berlekamp 或 Cantor-Zassenhaus 的算法。

常量 k 的高级伪代码：

• 计算给定数字的 i 次方
• 减去得到未知数的 i 次幂之和。将总和称为 b_i。
• 使用牛顿恒等式从 b_i 计算系数;称他们为 C_I。基本上，c 1 = b₁;c 2 = （c 1b₁ - b 2）/₂;有关确切的公式，请参阅维基百科
• 因式分解多项式 x k-c 1 x^k-1 + ... + c^k。
• 多项式的根是所需的数字 a₁、...、_{a k}。

对于变 k，使用 Miller-Rabin 等方法找到素数 n <= q < 2n，并在所有数字约简模 q 的情况下执行这些步骤。

编辑：这个答案的先前版本指出，可以使用特征 2 的有限域 （q=2^（log n）），而不是 Z q，其中_q 是素数。事实并非如此，因为牛顿公式需要除以最多 k 的数字。

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

设乘积，P1 = 1 x 2 x 3 x .............50

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

两个误会项的乘积，a x b = P1 - P2。

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

从上面两个方程中，通过二次方程求解 a 和 b。A 和 B 是您缺少的数字。

这听起来可能很愚蠢，但是，在呈现给您的第一个问题中，您必须查看袋子中所有剩余的数字才能将它们实际相加以使用该方程式找到缺失的数字。

因此，既然您可以看到所有数字，只需查找缺少的数字即可。当缺少两个数字时也是如此。我觉得很简单。当您看到袋子中剩余的数字时，使用方程式是没有意义的。

基于数字总和的解决方案的问题在于，它们没有考虑存储和处理具有大指数的数字的成本......在实践中，为了让它适用于非常大的 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^jceil(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))

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

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

例如，面试官可能要发送消息，需要知道哪些消息没有导致回复，并且需要在第条回复到达后尽可能短的挂钟时间内知道它。我们还要假设消息通道的性质是这样的，即使以全功率运行，也有足够的时间在消息之间进行一些处理，而不会对在最后一次回复到达后产生最终结果所需的时间产生任何影响。这段时间可以用来将每条已发送消息的一些识别方面插入到一个集合中，并在每个相应的回复到达时将其删除。到达最后一个回复后，唯一要做的就是从集合中删除其标识符，这在典型的实现中需要 .之后，该集合包含缺失元素的列表，无需进行其他处理。nkn-kO(log k+1)k

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

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

你有一个-位长整数（因此是空格），你在其中添加 ，其中 x 是你在袋子里找到的下一个数字： 这需要时间（这对面试官来说不是问题）。最后，你会得到你要找的最大数字。然后，您再次执行上述操作：klog8(k)x^2s=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;
}

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

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

假设 “bag” 由一个从 1 开始的大小数组表示，我们可以在时间和附加空间中求解 Qk。A[]N - kO(N)O(k)

首先，我们通过元素扩展数组，使其现在的大小为 。这是额外的空间。然后，我们运行以下伪代码算法：A[]kNO(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

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

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

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

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

也许这个算法可以适用于问题 1：

1. 预计算前 100 个整数的异或（val=1^2^3^4....100）
2. 异或元素，因为它们不断来自输入流 （ val1=val1^next_input）
3. 最终答案=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 中的任何设置位。假设该位设置为 val。这意味着 a1 和 a2 在位位置具有不同的奇偶校验。 现在我们对原始数组进行另一次迭代并保留两个 xor 值。一个用于设置了第 i 位的数字，另一个用于未设置第 i 位的数字。我们现在有两个数字桶，它保证将位于不同的桶中。现在重复我们在每个存储桶上查找一个缺失元素的相同操作。ithitha1 and a2

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

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

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

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

然后遍历 .如果元素保持 false，则元素 + 1 的索引是缺失的数字。例如，如果为 false，则我们知道缺少数字 45。boolArrayboolArray[44]

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

因此，此解决方案可以用于从给定的连续数字集中查找任何缺失的数字。

我认为这可以在没有任何复杂的数学方程式和理论的情况下完成。以下是对就地和 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]

此解决方案的关键是通过在遍历数组时否定该 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;
    }

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

    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-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);
        }
    }
}

// Size of numbers
def n=100;

// A list of numbers that is missing k numbers.
def list;

// A map
def 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 numbers
println("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) then
        Find the missing number or numbers
}

迭代这个循环，你很容易得到答案。

我认为这可以概括为：

将 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，而你只有两个方程可以求解。

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

这是一个非常简单的问题

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 的结果）为您提供两个缺失的 nos i 的 xor。e a XOR b，如果 a 和 b 是缺失元素
   4.使用通常的求和公式 diff 方法获取缺失 No 的总和，假设 diff 为 d。

现在运行一个循环来获得可能的对 （p，q），它们都位于 [1， 100] 中，总和为 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 = 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 函数的复杂性，所以我无法计算出这个解决方案的复杂性（如果有人知道，请在下面发表评论。

关键是使用索引来标记某个数字是否在范围内。 在这里，我们知道我们有 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 array
                   arr[temp-1]=-1;
                   idx=temp-1;
              }
          }
      }
    }

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

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

您可以根据需要构建基本对称函数，方法是注意 .进一步的思考应该会让你相信这一点，依此类推，这样它们就可以一次性计算出来。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)0x_iz^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n

因此，我们可以构建多项式并尝试对其进行因式分解，以找出哪些数字不在集合中，正如其他人所提到的。

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

    //sort
    int missingNum[2];//missing 2 numbers- can be applied to more than 2
    int 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）缺失数字问题，您可以修改 quickselect，如果分区是就地完成的，则平均运行并使用常量内存。O(n)

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

2. 通过将透视值与每个分区的大小进行比较，确定 2 个缺失数字所在的分区 （ 和p - 1 - count(l) = count of missing numbers in ln - 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 个缺失的数字，该算法始终丢弃至少一个分区，因此它保留了快速选择的平均时间复杂度。同样，对于 3 个缺失的数字，此算法也会在每次传递时丢弃至少一个分区（因为与 2 个缺失数字一样，最多只有 1 个分区将包含多个缺失数字）。但是，我不确定添加更多缺失数字时性能会降低多少。O(n)

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

<?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);
    }
  }

演示

我已经使用 Java 8 和 Java 8 之前编写了代码。 它使用公式：（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

• 创建一个大小为 的数组 。au = k^2
• 选择任何通用哈希函数 .（如乘移h : {1,...,n} -> {1,...,u})
• 对于每增加一个i1, ..., na[h(i)] += i
• 对于输入流中的每个数字，递减 。xa[h(x)] -= x

如果所有缺失的数字都已散列到不同的存储桶，则数组的非零元素现在将包含缺失的数字。

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

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

事实上，通过使用注释中描述的技巧，我们可以比幂和法更有效率。

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

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

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

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

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

这是任意 k 的简单解决方案：对于数字集中的每个 v，累加 2^v 的总和。最后，将 i 从 1 循环到 N。如果 2^i 的按位和 AND 为零，则缺少 i。（或者从数字上讲，如果总和的下限除以 2^i 是偶数。或 .）sum modulo 2^(i+1)) < 2^i

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

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

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

您可以使用二进制搜索来查找缺失（或连续）数字的间隔。运行时间应约为 （num intervals） * log（avg interval length） * N. 如果间隔不多，则很有用。

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

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

计算并存储所有数字 1 到 100 的总和，将结果模 101 减少。Little 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,9
NMissing=3
arr_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 chipntest tubesxxmilliliter

假设我们的处理器是 .当我们点亮激光时，它会垂直于其长度穿过所有管子。每次通过化学液体时，光度都会降低。在某个毫升标记处通过光是 的操作。laser light1O(1)

现在，如果我们在试管的中间点亮激光并获得光度输出

• 等于预先计算的值（在没有缺少数字时计算），则缺少的数字大于 。n/2
• 如果我们的输出较小，则至少有一个小于 的缺失数字。我们还可以检查光度是否降低 或 。如果它减少，则一个缺失的数字小于，另一个大于。如果它减少，则两个数字都小于 。n/2121n/2n/22n/2

我们可以一遍又一遍地重复上述过程，缩小问题范围。在每个步骤中，我们都会将域缩小一半。最后，我们可以得到我们的结果。

值得一提的并行算法（因为它们很有趣），

• 通过一些并行算法进行排序，例如，并行合并可以及时完成。然后可以通过二进制搜索及时找到缺失的数字。O(log^3 n)O(log n)
• 从理论上讲，如果我们有处理器，那么每个进程都可以检查其中一个输入并设置一些标识数字的标志（方便地在数组中）。在下一步中，每个进程都可以检查每个标志，并最终输出未标记的数字。整个过程需要时间。它有额外的空间/内存要求。nO(1)O(n)

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

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

假设我们有数字 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)

现在结果包含没有丢失的数字（误报）。但是当缺少元素时，k <=（结果的大小）<= n。resultk

我将最后一次浏览给定的列表，以标记结果是否缺失。

所以时间复杂度将为 O（n） 。

最后，可以通过将节点,,,而不是 和 来减少误报的数量（以及所需的空间）。0001111001

假设一个 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

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

在另一个循环中，打印包含 AKA 缺少的元素的元素的索引。forfalse

时间复杂度：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 和 Colonel Panic 那样更改输入数组，也不会像 Chris Lercher、JeremyP 和许多其他人那样使用巨大的位集。基本上，我从 Svalorzen/Gilad Deutch 对 Q2 的想法开始，将其推广到常见情况 Qk，并在 Java 中实现以证明该算法有效。

理念

假设我们有一个任意区间 I，我们只知道它包含至少一个缺失的数字。在输入数组中经过一次后，仅查看 I 中的数字，我们可以从 I 中获取缺失数字的总和 S 和数量 Q。为此，我们只需在每次遇到 I 中的数字（用于获得 Q）时减小 I 的长度，并将 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 永远不会大于缺失数 count k。不等式 p <= k 可以被严格证明。另一方面，还有一个经验上限 p <对数₂N + 3，对于较大的 k 值很有用。我们需要对输入数组的每个数字进行二进制搜索，以确定它所属的区间。这会将对数 k 乘数添加到时间复杂度中。

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

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

Java 实现

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

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;
    }
}

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

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);
    }
}

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

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 个最高有效数字的数字计数。即

= [__,__,__,__] 
   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

赋予动机

如果你想解决一般情况的问题，并且你可以存储和编辑数组，那么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

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

法典

C 风格的解决方案（不要因为全局变量而评判我，我只是想让代码对非 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)sumn(n-1)/2n-1kO(1)

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

m 1 -- 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（ x_i ）f

x 1 + x₂ + ... + x_k = z₁

x₁ 2 + x 2 ² + ... + x_k 2 = z ₂

............

............

............

x₁ k + x₂ k + ... + x k k = z ^k

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

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