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

查看:244
本文介绍了找到两名失踪数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

有一台机器与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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆