在阵列中找到2个缺失数字的最快方法

Question

这个问题的存在只是因为纯粹的好奇心.不是作业.

找到在数组1..n中找到两个缺失数字的最快方法

所以,在一篇相关的文章中:在一组数字中找到缺失数字的最快方法 我发现你可以通过总结和减去总数来快速完成.

但是2个数字怎么样？

所以,我们的选择是:

1. 顺序搜索
2. 总结项目,从1..n中的所有项目中减去总数,然后搜索所有可能的案例.

还要别的吗？可能有O(n)解决方案吗？我在其中一个网站的ruby部分找到了这个,但是考虑了任何语言(除非语言有一些特定的东西)

Answer 1

1. 找到数字的总和S=a1+...+an.
2. 还可以找到平方和T=a1*a1+...+an*an.
3. 你应该知道总和应该是 S'=1+...+n=n(n+1)/2
4. 你知道方格的总和应该是T'=1^2+...+n^2=n(n+1)(2n+1)/6.
5. 现在建立以下方程组 x+y=S'-S,x^2+y^2=T'-T.
6. 通过写x^2+y^2=(x+y)^2-2xy=>来解决xy=((S'-S)^2-(T'-T))/2.而现在这些数字仅仅是二次方的根源z:z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.

Answer 2

简单的方法(也很快:)

a = [1,2,3,5,7]
b = (1..7).to_a
p b-a #=> [4, 6]

Answer 3

假设数组为[1,4,2,3,7].缺少的数字是5,6

第1步:添加数组中的所有数字.17.我们知道总和为1..7(n*(n + 1)/ 2)= 28.

因此x + y + 17 = 28 => x + y = 11

第2步:将数组中的所有数字相乘.我们知道1..7 = 5040的乘积.

因此x*y*168 = 5040 => x*y = 30

(x+y)^2 = x^2 + 2xy + y^2 
=> 121 = 60 + x^2 + y^2
=> x^2 + y^2 = 61

(x-y)^2 = x^2 - 2xy + y^2 
=> (x-y)^2 = 61 - 60
=> (x-y)^2 = 1 
=> x-y = 1

我们有x + y = 11和xy = 1.求解x,y.

该解决方案不需要额外的存储空间,并且在O(n)中完成.