您会得到 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/
如果数组中存在所有数字,则总和为N(N+1)/2。
N(N+1)/2
通过对O(n)中数组中的所有数字求和来确定实际总和,让它为Sum(Actual)。
Sum(Actual)
缺少一个数字,设为j,重复一个数字,设为k。那意味着
j
k
总和(实际)= N(N + 1)/ 2 + k-j
从中得出
k =总和(实际)-N(N + 1)/ 2 + j
此外,我们可以计算在阵列中平方的总和,这将总结为n 3 /3 + N 2 /2 + N / 6,如果所有数字是本。
现在我们可以计算O(n)中的平方和Sum(Actual Squares)。
Sum(Actual Squares)
总和(实际方)= N 3 /3 + N 2 /2 + N / 6 + K 2 - J 2
现在我们有了两个方程,可以用来确定j和k。