我们有一台内存为O(1)的计算机，我们希望在第一遍中传递n数字(一个接一个)，然后排除这两个数字，然后将n-2数字传递给该计算机。
编写查找缺失数字的算法。
最佳答案
可以使用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。