我相信我有一个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)因素的时间复杂度

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它，比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案，但如果我在这种情况下面临这样的任务(已知边界，低边界)，这是我在现实生活中会使用的解决方案。如果数字集非常大，那么我当然会考虑一个更有效的算法，但在此之前，简单的解决方案对我来说已经足够了。

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

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.

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

我们可以把问题简化为

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

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

代换给我们:

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

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

您可以使用二分搜索来查找缺失(或连续)数字的间隔。运行时间应该是(num间隔)* log(平均间隔长度)* n。如果间隔不多，则很有用。