我已经阅读了所有30个答案，并找到了最简单的一个，即使用100位数组是最好的。但正如问题所说，我们不能使用大小为N的数组，我将使用O(1)空间复杂度和k次迭代，即O(NK)时间复杂度来解决这个问题。

为了让解释更简单，假设给了我从1到15的数字，其中两个少了，即9和14，但我不知道。让包看起来像这样:

,1,2,12,4,7,5,10,11,13,15,3,6 [8].

我们知道每个数字在内部都是以位的形式表示的。 对于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的位数组，其中包含具有对应的两位最高位的数字的计数。即

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

从左到右扫描袋子，填充上面的数组，使比特数组的每个bin都包含数字的计数。结果如下:

= [ 3, 4, 3, 3] 
   00,01,10,11

如果所有的数字都出现了，它看起来会是这样的:

= [ 3, 4, 4, 4] 
   00,01,10,11

因此，我们知道有两个数字缺失了:一个数字的最高两位有效位数是10，另一个数字的最高两位有效位数是11。现在再次扫描列表，并为下两位有效数字填写一个大小为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

我认为这不需要任何复杂的数学方程和理论。下面是一个建议的到位和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;
    }

你能查一下每个号码是否都存在吗?如果是，你可以试试这个:

S =袋子中所有数字的和(S < 5050) Z =缺失数的和5050 - S

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

x = Z - y和 max(x) = Z - 1

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

免责声明:我已经读了这个问题好几天了，但我的知识超出了我对数学的理解。

我试着用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

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

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

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值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。