给你一个数组N64 位整数。 N可能非常大。您知道每个整数 1..N 在数组中都会出现一次，除了有一个整数缺失和一个整数重复。
编写一个线性时间算法来查找丢失和重复的数字。此外，您的算法应该在较小的恒定空间中运行，并且保持数组不变。
Source: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/
如果数组中存在所有数字，则总和将为N(N+1)/2.
通过在 O(n) 内对数组中的所有数字求和来确定实际总和，令其为Sum(Actual).
缺少一个号码，就这样吧j并且有一个数字重复，令此为k。这意味着
总和（实际）= N(N+1)/2 + k - j
由此衍生出
k = 总和（实际）-N(N+1)/2 + j
Also we can calculate the sum of squares in the array, which would sum up to
n3/3 + n2/2 + n/6 if all numbers were present.
现在我们可以计算 O(n) 中的实际平方和，令其为Sum(Actual Squares).
Sum(Actual Squares) =n3/3 +
n2/2 + n/6 + k2
- j2
现在我们有两个方程可以确定j and k.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
