找到两个缺少的数字

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位,因为您要存储两个输入整数的乘积,并且在一种情况下将这些值中的一个乘以2.