c++ - 找到两个缺失的数字

Question

我们有一台 O(1) 内存的机器，我们想在第一遍中传递 n 个数字(一个接一个)，然后排除这两个数字，我们将传递 n-2 个号码给机器。

编写一个算法来查找缺失的数字。

Answer 1

可以用 O(1) 内存完成。

您只需要几个整数来跟踪一些运行总和。整数不需要 log n 位(其中 n 是输入整数的数量)，它们只需要 2b+1 位，其中 b 是单个输入整数中的位数。

当您第一次读取流时，将所有数字及其所有正方形相加，即对于每个输入数字 n，执行以下操作:

sum += n
sq_sum += n*n

然后在第二个流上对两个不同的值 sum2 和 sq_sum2 执行相同的操作。现在做以下数学运算:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

您在所有中间结果中需要 2b+1 位，因为您要存储两个输入整数的乘积，并且在一种情况下将这些值之一乘以二。