java - 在 O(n) 时间内找到数组中的重复元素

Question

我在一次工作面试中被问到这个问题，我一直想知道正确的答案。

You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time O(n)?

例如，4,1,2,3 的数组将变为 4,1,2,2。

时间O(n²)的简单解决方法是使用嵌套循环查找每个元素的重复项。

Answer 1

这可以在 O(n) 中完成时间和O(1)空间。

(该算法之所以有效，是因为数字是已知范围内的连续整数):

在一次遍历 vector 中，计算所有数字的总和，以及所有数字的平方和。

从N(N-1)/2 中减去所有数字的总和.调用 A .

从N(N-1)(2N-1)/6 中减去平方和.将其除以 A .调用结果B .

被删除的号码是(B + A)/2它被替换的数字是(B - A)/2 .

示例:

vector 是[0, 1, 1, 2, 3, 5] :

• N = 6

• vector 之和为 0 + 1 + 1 + 2 + 3 + 5 = 12。N(N-1)/2 为 15。A = 3。

• 平方和是 0 + 1 + 1 + 4 + 9 + 25 = 40。N(N-1)(2N-1)/6 是 55。B = (55 - 40)/A = 5。

• 被删除的数字是 (5 + 3)/2 = 4。

• 它被替换的数字是 (5 - 3)/2 = 1。

为什么有效:

• 原 vector 之和[0, ..., N-1]是 N(N-1)/2 .假设值 a被删除并替换为 b .现在修改后的 vector 的总和将是 N(N-1)/2 + b - a .如果我们从 N(N-1)/2 中减去修改后的 vector 的和我们得到 a - b .所以A = a - b .

• 同理，原 vector 的平方和为N(N-1)(2N-1)/6 .修改后 vector 的平方和为N(N-1)(2N-1)/6 + b<sup>2</sup> - a<sup>2</sup> .从原始总和中减去修改 vector 的平方和得到 a<sup>2</sup> - b<sup>2</sup> , 与 (a+b)(a-b) 相同.因此，如果我们将其除以 a - b (即 A )，我们得到 B = a + b .

• 现在B + A = a + b + a - b = 2a和 B - A = a + b - (a - b) = 2b .