我试图弄清楚这个问题遇到了很多麻烦，而这个问题的根源是创建一个复杂的算法。这是我正在努力解决的问题：O(n)
长度数组包含范围 中的整数。但是，它只包含不同的数字。因此，其中一个数字丢失，另一个数字重复。编写一个Java方法，该方法作为输入参数并返回缺少的数字;该方法应在 中运行。
An[0, .., n - 1]n - 1AO(n)例如，当 ，应返回 ;当 时，应返回 。
A = [0, 2, 1, 2, 4]oddOneOut()3A = [3, 0, 0, 4, 2, 1]oddOneOut()5
显然，这是一个很容易用算法解决的问题，（最有可能的是，我只是没有看到它！我试图使用各种方法解决它，但无济于事。我试图用Java解决它，但如果你更愿意用Python解决它，那也没关系。O(n2)O(n)
提前感谢您...
假设缺少的数字是 ，而重复的数字是 。如果将所有数字相加，则总和将为：xy
(n - 1) * n / 2 - x + y
从上面，你可以找到.....(1)(x - y)
同样，对数字的平方求和。然后，总和将为：
(n - 1) * n * (2 * n - 1) / 6 - x2 + y2
从上面你得到....(2)(x2 - y2)
(2) / (1) gives (x + y).....(3)
（1） + （3） 给出，你可以因此找到 和 。2 * xxy
请注意，在此解决方案中，有 O（1） 个额外的存储，并且是 O（n） 个时间复杂度。上面的其他解决方案是不必要的额外存储。O(n)
混合 C/C++中的代码，以便更清晰一些：
#include <stdio.h>
int findDup(int *arr, int n, int& dup, int& missing)
{
int sum = 0;
int squares = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
squares += arr[i] * arr[i];
}
sum = (n - 1) * n / 2 - sum; // x - y
squares = (n - 1) * n * (2 * (n - 1) + 1) / 6 - squares; // x^2 - y^2
if (sum == 0) {
// no duplicates
missing = dup = 0;
return -1;
}
missing = (squares / sum + sum) / 2; // ((x^2 - y^2) / (x - y) + (x - y)) / 2 = ((x + y) + (x - y)) / 2 = x
dup = missing - sum; // x - (x - y) = y
return 0;
}
int main(int argc, char *argv[])
{
int dup = 0;
int missing = 0;
int a[] = {0, 2, 1, 2, 4};
findDup(a, sizeof(a) / sizeof(int), dup, missing);
printf("dup = [%d], missing = [%d]\n", dup, missing);
int b[] = {3, 0, 0, 4, 2, 1};
findDup(b, sizeof(b) / sizeof(int), dup, missing);
printf("dup = [%d], missing = [%d]\n", dup, missing);
return 0;
}
输出：
dup = [2], missing = [3]
dup = [0], missing = [5]
一些python代码：
def finddup(lst):
sum = 0
sumsq = 0
missing = 0
dup = 0
for item in lst:
sum = sum + item
sumsq = sumsq + item * item
n = len(a)
sum = (n - 1) * n / 2 - sum
sumsq = (n - 1) * n * (2 * (n - 1) + 1) / 6 - sumsq
if sum == 0:
return [-1, missing, dup]
missing = ((sumsq / sum) + sum) / 2
dup = missing - sum
return [0, missing, dup]
found, missing, dup = finddup([0, 2, 1, 2, 4])
if found != -1:
print "dup = " + str(dup) + " missing = " + str(missing)
print finddup([3, 0, 0, 4, 2, 1])
输出：
dup = 2 missing = 3
[-1, 0, 0]
迭代数组两次：这仍然是 O（n）。创建一个布尔值（或 Java BitSet）的临时数组来保存您获得的数字。第二次执行循环时，请检查布尔数组中是否有孔。
