algorithm - 在线性时间和常数空间中查找数组中缺失和重复的元素

Question

你得到了一个 N 64 位整数数组。 N 可能很大。你知道每个整数 1..N 在数组中出现一次，除了有一个整数缺失和一个整数重复。

编写一个线性时间算法来查找缺失和重复的数字。此外，您的算法应在较小的常量空间内运行，并保持数组不变。

来源:http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

Answer 1

如果数组中存在所有数字，则总和将为 N(N+1)/2。

通过在 O(n) 中对数组中的所有数字求和来确定实际总和，令其为 Sum(Actual)。

缺少一个数字，设为j，一个数字重复，设为k。也就是说

Sum(Actual) = N(N+1)/2 + k - j

从那个派生

k = Sum(Actual) -N(N+1)/2 + j

我们还可以计算数组中的平方和，总和为n³/3 + n²/2 + n/6 如果所有数字都存在。

现在我们可以在 O(n) 中计算实际平方和，令其为 Sum(Actual Squares)。

Sum(Actual Squares) =n³/3 + n²/2 + n/6 + k² - j²

现在我们有两个方程可以用来确定j 和k。