您还可以创建一个大小为last_element_in_the_existing_array + 1的布尔数组。

在for循环中，标记现有数组中存在的所有元素为true。

在另一个for循环中，打印包含false的元素的索引，即缺失的元素。

时间复杂度:O(last_element_in_the_existing_array)

空间复杂度:O(array.length)

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

    //sort
    int missingNum[2];//missing 2 numbers- can be applied to more than 2
    int j = 0;    
    for(int i = 0; i < length - 1; i++){
        if(arr[i+1] - arr[i] > 1 ) {
            missingNum[j] = arr[i] + 1;
            j++;
        }
    }

如果一个数字只出现一次，用下面的方法很容易分辨:

创建一个大小为给定数字的布尔数组boolArray;这里是100。

遍历输入数字，并根据数字值将一个元素设置为true。例如，如果找到45，则设置boolArray[45-1] = true;

这是一个O(N)运算。

然后循环遍历boolArray。如果一个元素保持为false，那么element + 1的下标就是缺失的数字。例如，如果boolArray[44]为false，我们就知道第45号丢失了。

这是O(n)运算。空间复杂度为O(1)。

所以这个解可以从一个给定的连续数集中找到任何缺失的数。

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

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

我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。