这里有一个解决方案，使用k位额外的存储空间，没有任何聪明的技巧，只是简单。执行时间O (n)，额外空间O (k)。只是为了证明这个问题可以解决，而不需要先阅读解决方案或成为天才:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

你已经知道这个和了，a + b = S1。

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。

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

计算这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 如果是，我们就完成了。

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

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

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

对于Q2，这是一个比其他解决方案效率更低的解决方案，但仍然有O(N)个运行时和O(k)个空间。

这个想法是运行原始算法两次。在第一个例子中，你得到了缺失的总数，这给了你缺失数字的上界。我们称这个数为N，你知道这两个数的和是N，所以第一个数只能在[1,floor((N-1)/2)]区间内，而第二个数将在[floor(N/2)+1,N-1]区间内。

因此，再次循环所有数字，丢弃第一个间隔中不包括的所有数字。你可以记录它们的和。最后，你将知道丢失的两个数字中的一个，进而知道第二个数字。

我有一种感觉，这种方法可以被推广，也许在一次输入传递期间，多个搜索可以“并行”运行，但我还没有弄清楚如何做到这一点。

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