我已经阅读了所有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

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

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

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

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

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

关键是使用索引来标记范围内是否存在某个数字。 这里我们知道从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时，我们必须小心。

有一个通用的方法来解决这样的流问题。 我们的想法是使用一些随机化，希望将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。

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

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

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

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