你可以试试布卢姆滤镜。将袋子中的每个数字插入到bloom中，然后遍历完整的1-k集，直到报告每个数字都没有找到。这可能不是在所有情况下都能找到答案，但可能是一个足够好的解决方案。

You can motivate the solution by thinking about it in terms of symmetries (groups, in math language). No matter the order of the set of numbers, the answer should be the same. If you're going to use k functions to help determine the missing elements, you should be thinking about what functions have that property: symmetric. The function s_1(x) = x_1 + x_2 + ... + x_n is an example of a symmetric function, but there are others of higher degree. In particular, consider the elementary symmetric functions. The elementary symmetric function of degree 2 is s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n, the sum of all products of two elements. Similarly for the elementary symmetric functions of degree 3 and higher. They are obviously symmetric. Furthermore, it turns out they are the building blocks for all symmetric functions.

你可以通过注意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。初等对称函数也出现在这里，这并不奇怪，因为多项式应该保持不变，如果我们对根进行任何排列。

所以我们可以建立一个多项式，并尝试因式分解来找出哪些数不在集合中，就像其他人提到的那样。

Finally, if we are concerned about overflowing memory with large numbers (the nth symmetric polynomial will be of the order 100!), we can do these calculations mod p where p is a prime bigger than 100. In that case we evaluate the polynomial mod p and find that it again evaluates to 0 when the input is a number in the set, and it evaluates to a non-zero value when the input is a number not in the set. However, as others have pointed out, to get the values out of the polynomial in time that depends on k, not N, we have to factor the polynomial mod p.

我认为这不需要任何复杂的数学方程和理论。下面是一个建议的到位和O(2n)时间复杂度的解决方案:

输入表格假设:

袋子里的数字# = n

缺失数字的数量= k

袋子里的数字由长度为n的数组表示

算法的输入数组长度= n

数组中缺失的条目(从袋子中取出的数字)将被数组中第一个元素的值替换。

如。最初袋子看起来像[2,9,3,7,8,6,4,5,1,10]。 如果4被取出，value 4将变成2(数组的第一个元素)。 因此，在取出4后，袋子将看起来像[2,9,3,7,8,6,2,5,1,10]

此解决方案的关键是在遍历数组时，通过对索引处的值求负来标记访问数的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;
    }

动机

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

谢谢你这个有趣的问题:

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

请参考牛顿恒等式

As变量的数量=方程的数量(必须为一致性)

我认为，对于这个问题，我们应该提高袋数的幂，以便创建不同的方程。

我不知道，但是，我相信如果有一个函数，比如f，我们要加上f(xi)

x1+x2+…+ xk = z1

x12 + x22 + ... + xk2 = z2

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

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

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

x1k + x2k + ... + xkk = XP

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

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

有一个通用的方法来解决这样的流问题。 我们的想法是使用一些随机化，希望将k个元素“分散”到独立的子问题中，在那里我们的原始算法为我们解决了问题。该技术用于稀疏信号重建等。

创建一个大小为u = k^2的数组a。 选取任意通用哈希函数h:{1，…，n} ->{1，…，u}。(如multiply-shift) 对于1中的每一个i，…， n增加a[h(i)] += i 对于输入流中的每个数字x，减去a[h(x)] -= x。

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

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

注意，这个算法占用k^2 logn位的空间(每个数组桶需要logn位)。这与@Dimitris Andreou的答案所需要的空间相匹配(特别是多项式因式分解的空间要求，它碰巧也是随机的。) 该算法每次更新的时间也是常数，而不是幂和情况下的时间k。

事实上，通过使用评论中描述的技巧，我们甚至可以比幂和法更有效。