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

我不知道这是否有效，但我想建议这个解决方案。

计算这100个元素的xor 计算98个元素的xor(在2个元素被移除之后) 现在(1的结果)XOR(2的结果)给你两个缺失的no的XOR，如果a和b是缺失的元素 4.用常用的求和公式diff得到缺失的no的和，我们设diff是d。

现在运行一个循环，得到可能的对(p,q)，它们都位于[1,100]，和为d。

当获得一对时，检查(3的结果)是否XOR p = q 如果是，我们就完成了。

如果我错了，请纠正我，如果这是正确的，也请评论时间复杂性

等一下。正如问题所述，袋子里有100个数字。无论k有多大，问题都可以在常数时间内解决，因为您可以使用一个集合，并在最多100k次循环迭代中从集合中删除数字。100是常数。剩下的数就是你的答案。

如果我们将解推广到从1到N的数字，除了N不是常数外，没有什么变化，所以我们在O(N - k) = O(N)时间内。例如，如果我们使用位集，我们在O(N)时间内将位设置为1，遍历这些数字，将位设置为0 (O(N-k) = O(N))，然后我们就得到了答案。

It seems to me that the interviewer was asking you how to print out the contents of the final set in O(k) time rather than O(N) time. Clearly, with a bit set, you have to iterate through all N bits to determine whether you should print the number or not. However, if you change the way the set is implemented you can print out the numbers in k iterations. This is done by putting the numbers into an object to be stored in both a hash set and a doubly linked list. When you remove an object from the hash set, you also remove it from the list. The answers will be left in the list which is now of length k.

还有一种方法是使用残差图滤波。

假设数字1到4少了3。二进制表示如下:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

我可以创建一个像下面这样的流程图。

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

注意，流图包含x个节点，而x是比特数。最大边数是(2*x)-2。

因此，对于32位整数，它将占用O(32)空间或O(1)空间。

现在如果我从1,2,4开始移除每个数的容量那么我就剩下了一个残差图。

0 ----------> 1 ---------> 1

最后我将像下面这样运行一个循环，

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

现在的结果是结果中包含的数字也没有缺失(假阳性)。但是当有k个缺失元素时，k <=(结果的大小)<= n。

我将最后一次检查给定的列表，以标记缺少或没有的结果。

所以时间复杂度是O(n)

最后，可以通过选取节点00、01、11、10而不是0和1来减少误报的数量(以及所需的空间)。

我们可以用O(log n)来做Q1和Q2。

假设我们的存储芯片由n个试管阵列组成。试管中的数字x用x毫升化学液体表示。

假设我们的处理器是一束激光。当我们点燃激光时，它垂直穿过所有的管子。每次它通过化学液体，光度就降低1。在某毫升处通过光是O(1)的运算。

现在如果我们在试管的中间点上激光就会得到光度的输出

等于预先计算的值(当没有数字缺失时计算)，则缺失的数字大于n/2。 如果我们的输出更小，那么至少有一个小于n/2的数字缺失。我们也可以检查光度是否降低了1或2。如果它减少1，那么一个缺失数小于n/2，另一个大于n/2。如果它减2，那么两个数都小于n/2。

我们可以一次又一次地重复上述过程，缩小我们的问题域。在每一步中，我们将定义域缩小一半。最后我们可以得到结果。

值得一提的是并行算法(因为它们很有趣)，

sorting by some parallel algorithm, for example, parallel merge can be done in O(log^3 n) time. And then the missing number can be found by binary search in O(log n) time. Theoretically, if we have n processors then each process can check one of the inputs and set some flag that identifies the number(conveniently in an array). And in the next step each process can check each flag and finally output the number that is not flagged. The whole process will take O(1) time. It has additional O(n) space/memory requirement.

请注意，如上所述，上面提供的两个并行算法可能需要额外的空间。

我让一个4岁的孩子来解决这个问题。他把数字分类，然后开始数。这有一个O(厨房地板)的空间要求，它的工作就像许多球丢失一样简单。