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

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

也许这个算法可以解决问题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.

我会用另一种方法来回答这个问题，询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求，显而易见的基于集的解决方案可能是正确的，而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

这当然不是批处理预先生成的数字袋的最快方法，因为整个过程运行O((log 1 + log 2 +…)+ log n) + (log n + log n-1 +…+ log k))。但它确实适用于任何k值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

您可能需要澄清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)空间中有多少是合适的，以及需要多长时间才能将所需大小的数字相加?

对于不同的k值，方法将是不同的，所以不会有一个关于k的通用答案。例如，对于k=1，可以利用自然数和，但对于k= n/2，必须使用某种bitset。对于k=n-1也是一样，我们可以简单地将袋子里唯一的数字与其他数字进行比较。

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

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