在时间 O（n）中查找数组中的重复元素

arrays algorithm java

2022-08-31 15:14:55

我在求职面试中被问到这个问题，我一直在想正确的答案。

您有一个从 0 到 n-1 的数字数组，其中一个数字被删除，并替换为数组中已有的数字，该数字与该数字重复。我们如何在时间O（n）中检测到这种重复？

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

时间 O（n²） 的简单解决方案是使用嵌套循环来查找每个元素的副本。

答案 1

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

（该算法之所以有效，是因为数字是已知范围内的连续整数）：

在通过向量的单次传递中，计算所有数字的总和，以及所有数字的平方和。

从中减去所有数字的总和。称之为 .N(N-1)/2A

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

被删除的号码是，它被替换的号码是。(B + A)/2(B - A)/2

例：

向量是：[0, 1, 1, 2, 3, 5]

原始向量的总和为。假设该值已被删除并替换为。现在，修改后的向量的总和将为。如果我们从中减去修改向量的总和，我们得到。所以。[0, ..., N-1]N(N-1)/2abN(N-1)/2 + b - aN(N-1)/2a - bA = a - b
同样，原始向量的平方和为。修改向量的平方和为。从原始和中减去修正向量的平方和，得到，这与相同。因此，如果我们将其除以（即），我们得到。N(N-1)(2N-1)/6N(N-1)(2N-1)/6 + b² - a²a² - b²(a+b)(a-b)a - bAB = a + b
现在和 .B + A = a + b + a - b = 2aB - A = a + b - (a - b) = 2b

答案 2

我们有原始数组创建第二个数组类型为。迭代第一个数组并设置 if 是 false，否则 bing！int A[N];bool B[N]bool=falseB[A[i]]=true