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

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值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

这可能听起来很愚蠢，但是，在第一个问题中，你必须看到袋子里所有剩下的数字，然后用这个方程把它们加起来，找到缺失的数字。

既然你能看到所有的数字，那就找出少了的那个数字。当缺少两个数字时也是如此。我觉得很简单。当你看到袋子里剩下的数字时，用方程就没有意义了。

不确定，这是否是最有效的解决方案，但我会遍历所有条目，并使用bitset来记住，设置了哪些数字，然后测试0位。

我喜欢简单的解决方案，我甚至相信，它可能比计算和，或平方和等更快。

我们可以使用下面的简单代码来查找重复的和缺失的值:

    int size = 8;
    int arr[] = {1, 2, 3, 5, 1, 3};
    int result[] = new int[size];

    for(int i =0; i < arr.length; i++)
    {
        if(result[arr[i]-1] == 1)
        {
            System.out.println("repeating: " + (arr[i]));
        }
        result[arr[i]-1]++;
    }

    for(int i =0; i < result.length; i++)
    {
        if(result[i] == 0)
        {
            System.out.println("missing: " + (i+1));
        }
    }

您可以使用二分搜索来查找缺失(或连续)数字的间隔。运行时间应该是(num间隔)* log(平均间隔长度)* n。如果间隔不多，则很有用。

你可以解出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

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