一个可能的解决方案:

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

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

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

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

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

这是个很简单的问题

void findMissing(){
    bool record[N] = {0};
    for(int i = 0; i < N; i++){
        record[bag[i]-1] = 1;
    }
    for(int i = 0; i < N; i++){
        if(!record[i]) cout << i+1 << endl;
    }
}

O(n)时间和空间复杂度

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

你可以解出Q2如果你有两个链表的和和和两个链表的乘积。

(l1为原始列表，l2为修改后的列表)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

我们可以优化它，因为等差级数的和是第一项和最后一项的平均值的n倍:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

现在我们知道(如果a和b是被移除的数字):

a + b = d
a * b = m

所以我们可以重新排列为:

a = s - b
b * (s - b) = m

然后乘出来:

-b^2 + s*b = m

然后重新排列，使右边为零

-b^2 + s*b - m = 0

然后用二次公式求解:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Python 3示例代码:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

我不知道根号，减法和求和函数的复杂性，所以我无法计算出这个解决方案的复杂性(如果有人知道，请在下面评论)。

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