小编典典

在线性时间和恒定空间中找到数组中丢失和重复的元素

algorithm

您会得到 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/


阅读 200

收藏
2020-07-28

共1个答案

小编典典

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

通过对O(n)中数组中的所有数字求和来确定实际总和,让它为Sum(Actual)

缺少一个数字,设为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)

总和(实际方)= N 3 /3 + N 2 /2 + N / 6 + K 2 - J 2

现在我们有了两个方程,可以用来确定jk

2020-07-28