ruby - 在数组中找到 2 个缺失数字的最快方法

Question

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

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

因此，在相关帖子中:Quickest way to find missing number in an array of numbers我发现你可以通过总和和减去总数来很快地做到这一点。

但是 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 .