关键是使用索引来标记范围内是否存在某个数字。 这里我们知道从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 如果是，我们就完成了。

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

也许这个算法可以解决问题1:

预计算前100个整数的xor (val=1^2^3^4....100) 对来自输入流的元素进行Xor (val1=val1^next_input) 最终的答案= val ^ val1

或者更好:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

这个算法实际上可以扩展到两个缺失的数字。第一步还是一样。当我们调用缺少两个数字的GetValue时，结果将是a1^a2是缺少的两个数字。让说

跌倒 = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.

等一下。正如问题所述，袋子里有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.

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

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

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

我们可以用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.

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