找到两名失踪数 [英] Find two missing numbers

问题描述

有一台机器与O（1）内存。 我们想通过n个（一一）第一次， 我们再次排除两个号码，我们将通过正2人至机器。 写一个算法，发现缺号。 这是一个面试问题，我解决不了了。

have a machine with O(1) memory. we want to pass n number (one by one) first time, and again we exclude two numbers and we will pass n-2 of them to machine. write an algorithm that finds missing numbers. This was an interview question and I couldn't solve it.

推荐答案

它可以与O（1）的内存来完成。

您只需要几个整数要保持一定数额的运行轨道。整数不需要日志n位（其中n是输入整数的个数），它们只要求2b中+ 1位，其中b是在个体中输入整数的位数。

You only need a few integers to keep track of some running sums. The integers do not require log n bits (where n is the number of input integers), they only require 2b+1 bits, where b is the number of bits in an individual input integer.

当你第一次读数据流添加所有的数字和他们所有的平方，即对每个输入数n，请执行以下操作：

When you first read the stream add all the numbers and all of their squares, i.e. for each input number, n, do the following:

sum += n
sq_sum += n*n

然后在第二个流做同样的事情，两个不同的值，SUM2和sq_sum2。现在做下面的数学：

Then on the second stream do the same thing for two different values, sum2 and sq_sum2. Now do the following maths:

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的值中的一个。

You need 2b+1 bits in all intermediate results because you are storing products of two input integers, and in one case multiplying one of those values by two.

这篇关于找到两名失踪数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！