动机

如果您想解决一般情况下的问题，并且可以存储和编辑数组，那么到目前为止，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)))

正如@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 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一定是缺失的。

我认为可以这样概括:

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

我相信我有一个O(k)时间和O(log(k)空间算法，前提是你有任意大整数的下限(x)和log2(x)函数:

你有一个k位的长整数(因此是log8(k)空间)，其中你加上x^2，其中x是你在袋子里找到的下一个数字:s=1^2+2^2+…这需要O(N)时间(这对面试官来说不是问题)。最后得到j= (log2(s))这是你要找的最大的数。然后s=s-j，重复上面的步骤:

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

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

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

预计算前100个整数的xor (val=1^2^3^4....100) 对来自输入流的元素进行Xor (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是缺少的两个数字。让说

跌倒 = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.

我还没有检查数学，但我怀疑在计算Σ(n)的同时计算Σ(n^2)将提供足够的信息来得到两个缺失的数字，如果有三个，也要计算Σ(n^3)，等等。