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

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

试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

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

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。

动机

如果您想解决一般情况下的问题，并且可以存储和编辑数组，那么到目前为止，Caf的解决方案是最有效的。如果您不能存储数组(流版本)，那么sdcvvc的答案是目前建议的唯一解决方案类型。

我建议的解决方案是最有效的答案(到目前为止在这个线程中)，如果你可以存储数组但不能编辑它，我从Svalorzen的解决方案中得到了这个想法，它解决了1或2个缺失的项目。该方案需要Θ(k*n)时间和O(min(k,log(n))和Ω(log(k))空间。它还可以很好地处理并行性。

概念

这个想法是，如果你使用原始的比较和的方法: sum = SumOf(1,n) - SumOf(数组)

．.． 然后取缺失数字的平均值: Average = sum/n_missing_numbers

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

Code

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)空间。请注意，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)个空间复杂度。

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

我会用另一种方法来回答这个问题，询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求，显而易见的基于集的解决方案可能是正确的，而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

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

这是个很简单的问题

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到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时，我们必须小心。