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

基于数字和的解决方案的问题是，它们没有考虑到存储和处理具有大指数的数字的成本……在实践中，为了使它适用于非常大的n，将使用大数库。我们可以分析这些算法的空间利用率。

我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度。

储存:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

所以l_j \in \ (j log n)

所使用的总存储空间:\sum_{j=1}^k l_j \in \Theta(k^2 log n)

使用的空间:假设计算a^j需要ceil(log_2 j)时间，总时间:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

总使用时间:\Theta(kn log n)

如果这个时间和空间是令人满意的，您可以使用一个简单的递归 算法。让b !I是袋子里的第I个元素，n个之前的数字 移除次数，k是移除次数。在Haskell语法中…

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

使用的存储:O(k)用于列表，O(log(n))用于堆栈:O(k + log(n)) 该算法更直观，具有相同的时间复杂度，占用的空间更少。

我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。

谢谢你这个有趣的问题:

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

请参考牛顿恒等式

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

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

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

x1+x2+…+ xk = z1

x12 + x22 + ... + xk2 = z2

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

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

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

x1k + x2k + ... + xkk = XP

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

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

您可能需要澄清O(k)的含义。

这里有一个任意k的简单解:对于你的数字集中的每一个v，将2^v相加。最后，循环i从1到n，如果和2^i按位和为零，则i缺失。(或者在数字上，如果和的底除以2^i是偶数。或者模2^(i+1) < 2^i

容易,对吧?O(N)时间，O(1)存储，支持任意k。

除了你在计算一个巨大的数字，在真正的计算机上，每个数字都需要O(N)个空间。事实上，这个解和位向量是一样的。

所以你可以很聪明地计算和，平方和和和立方体的和…直到v^k的和，然后用复杂的数学方法提取结果。但这些都是很大的数字，这就引出了一个问题:我们谈论的是哪种抽象的运作模式?O(1)空间中有多少是合适的，以及需要多长时间才能将所需大小的数字相加?

    //sort
    int missingNum[2];//missing 2 numbers- can be applied to more than 2
    int j = 0;    
    for(int i = 0; i < length - 1; i++){
        if(arr[i+1] - arr[i] > 1 ) {
            missingNum[j] = arr[i] + 1;
            j++;
        }
    }