给定一个大小为n的数组A [1..n]，它包含集合{1..n}中的元素。但是，缺少两个元素（也许重复了两个数组元素）。找到缺少的元素。
例如，如果n = 5，则A可以为A [5] = {1,2,1,3,2}; 因此缺少的元素是{4,5}
我使用的方法是：
int flag[n] = {0}; int i; for(i = 0; i < n; i++) { flag[A[i]-1] = 1; } for(i = 0; i < n; i++) { if(!flag[i]) { printf("missing: %d", (i+1)); }
空间复杂度为O（n）。我觉得这是一个非常开玩笑且效率低下的代码。因此，请您提供一种具有更好的时空复杂性的更好的算法。
从理论上讲
即使使用只读数组，也可以在O（1）空间（在RAM模型中，即O（1）字）和O（n）时间中进行操作。
警告：长期学习一些数学知识。如果您仅对代码感兴趣，而不对算法/证明感兴趣，请跳至代码部分。不过，您需要阅读算法部分的某些部分才能理解代码。
算法
假设缺少的数字是x和y。
数组有两种可能性：
1）一个数字重复三次，而数组中的其余数字恰好出现一次。
对于这种情况，桶装异或把戏将起作用。
对数组的所有元素与1,2，…，n进行XOR。
您最终得到z = x XOR y。
z的至少一位非零。
现在，基于该位（两个存储桶）区分数组元素，再次进行XOR穿过数组。
您将最终得到x和y。
一旦有了x和y，就可以确认它们是否确实是缺少的元素。
如果碰巧确认步骤失败，那么我们必须有第二种情况：
2）两个元素恰好重复两次，其余元素恰好出现一次。
令两个重复的元素为a和b（x和y为缺失的元素）。
警告：前面有数学。
让 S_k = 1^k + 2^k + .. + n^k
S_k = 1^k + 2^k + .. + n^k
例如S_1 = n(n+1)/2，S_2 = n(n+1)(2n+1)/6等
S_1 = n(n+1)/2
S_2 = n(n+1)(2n+1)/6
现在我们计算 7 件事情：
T_1 = Sum of the elements of the array = S_1 + a + b - x - y. T_2 = Sum of the squares = S_2 + a^2 + b^2 - x^2 - y^2 T_3 = Sum of cubes = S_3 + a^3 + b^3 - x^3 - y^3 T_4 = Sum of fourth powers = S_4 + a^4 + b^4 - x^4 - y^4 ... T_7 = Sum of seventh powers = S_7 + a^7 + b^7 - x^7 - y^7
注意，我们可以使用O（1）个单词（一个为整数）来处理溢出问题。（我估计8-10个字就足够了）。
让 Ci = T_i - S_i
Ci = T_i - S_i
现在假设a，b，x，y是四次多项式的根 P(z) = z^4 + pz^3 + qz^2 + rz + s
P(z) = z^4 + pz^3 + qz^2 + rz + s
现在我们尝试将上面的七个方程变换成四个线性方程p,q,r,s。
p,q,r,s
例如，如果我们这样做 4th Eqn + p * 3rd Eqn + q* 2nd equation + r* 1st equation
4th Eqn + p * 3rd Eqn + q* 2nd equation + r* 1st equation
我们得到
C4 + p*C3 + q*C2 + r*C1 = 0
同样，我们得到
C5 + p*C4 + q*C3 + r*C2 + s*C1 = 0 C6 + p*C5 + q*C4 + r*C3 + s*C2 = 0 C7 + p*C6 + q*C5 + r*C4 + s*C3 = 0
这是四个线性方程p,q,r,s，可通过线性代数技术（例如高斯消元法）求解。
请注意，这p,q,r,s将是有理数，因此只能使用整数算术来计算。
现在假设我们得到了p,q,r,s上述方程组的解决方案。
考虑一下P(z) = z^4 + pz^3 + qz^2 + rz + s。
上面的等式基本上是在说
P(a) + P(b) - P(x) - P(y) = 0 aP(a) + bP(b) - xP(x) -yP(y) = 0 a^2 P(a) + b^2 P(b) - x^2 P(x) - y^2 P(y) = 0 a^3 P(a) + b^3 P(b) - x^3 P(x) - y^3 P(y) = 0
现在矩阵
1 1 -1 -1 a b -x -y a^2 b^2 -x^2 -y^2 a^3 b^3 -x^3 -y^3
与范德蒙德矩阵具有相同的行列式，因此如果a,b,x,y是不同的，则是可逆的。
a,b,x,y
因此，我们必须做到这一点P(a) = P(b) = P(x) = P(y) = 0。
P(a) = P(b) = P(x) = P(y) = 0
现在检查的1,2,3,...,n根x^4 + px^3 + qx^2 + rx + s = 0。
1,2,3,...,n
x^4 + px^3 + qx^2 + rx + s = 0
因此，这是一个线性时间常数空间算法。
码
我写了下面的C＃（.Net 4.0）代码，它似乎对我尝试过的几个示例有用…（注意：我没有理会上面的情况1）。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace SOManaged { class Program { static void Main(string[] args) { ulong[] inp = {1,3,2,1,2}; ulong[] inp1 = { 1,2,3,4,5,6,7,8, 9,10,11,13,14,15, 16,17,18,19,20,21,5,14}; int N = 100000; ulong[] inp2 = new ulong[N]; for (ulong i = 0; i < (ulong)N; i++) { inp2[i] = i+1; } inp2[122] = 44; inp2[419] = 13; FindMissingAndRepeated(inp); FindMissingAndRepeated(inp1); FindMissingAndRepeated(inp2); } static void FindMissingAndRepeated(ulong [] nums) { BigInteger[] C = new BigInteger[8]; // Compute the C_i for (int k = 0; k < 8; k++) { C[k] = 0; } BigInteger i = 1; BigInteger n = 0; for (int j = 0; j < nums.Length; j++) { n = nums[j]; i = j + 1; for (int k = 1; k < 8; k++) { C[k] += i - n; n = n * nums[j]; i = i * (j + 1); } } for (int k = 1; k <= 7; k++) { Console.Write("C[" + k.ToString() + "] = " + C[k].ToString() +", "); } Console.WriteLine(); // Solve for p,q,r,s BigInteger[] pqrs = new BigInteger[4]; BigInteger[] constants = new BigInteger[4]; BigInteger[,] matrix = new BigInteger[4, 4]; int start = 4; for (int row = 0; row < 4; row++ ) { constants[row] = -C[start]; int k = start-1; for (int col = 0; col < 4; col++) { matrix[row, col] = C[k]; k--; } start++; } Solve(pqrs, matrix, constants, 4); for (int k = 0; k < 4; k++) { Console.Write("pqrs[" + k.ToString() + "] = " + pqrs[k].ToString() + ", "); } Console.WriteLine(); // Find the roots. for (int k = 1; k <= nums.Length; k++) { BigInteger x = new BigInteger(k); BigInteger p_k = x * x * x* x + pqrs[0] * x* x * x + pqrs[1] * x * x + pqrs[2] * x + pqrs[3]; if (p_k == 0) { Console.WriteLine("Found: " + k.ToString()); } } } // Solve using Cramer's method. // matrix * pqrs = constants. static void Solve(BigInteger[] pqrs, BigInteger[,] matrix, BigInteger[] constants, int n) { BigInteger determinant = Determinant(matrix, n); for (int i = 0; i < n; i++) { BigInteger[,] numerator = Replace(matrix, constants, n, i); BigInteger numDet = Determinant(numerator,4); pqrs[i] = numDet/ determinant; } } // Replace a column of matrix with constants. static BigInteger[,] Replace(BigInteger[,] matrix, BigInteger[] constants, int n, int col) { BigInteger[,] newMatrix = new BigInteger[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j != col) { newMatrix[i, j] = matrix[i, j]; } else { newMatrix[i, j] = constants[i]; } } } return newMatrix; } // Recursively compute determinant for matrix. static BigInteger Determinant(BigInteger[,] matrix, int n) { BigInteger determinant = new BigInteger(0); int multiplier = 1; if (n == 1) { return matrix[0,0]; } for (int i = 0; i < n; i++) { BigInteger [,] subMatrix = new BigInteger[n-1,n-1]; int row = 0; for (int j=1; j < n; j++) { int col = 0; for (int k = 0; k < n ; k++) { if (k == i) { continue; } subMatrix[row,col] = matrix[j,k]; col++; } row++; } BigInteger subDeterminant = Determinant(subMatrix, n - 1); determinant += multiplier * subDeterminant * matrix[0,i]; multiplier = -multiplier; } return determinant; } } }
输出是
C[1] = 6, C[2] = 36, C[3] = 180, C[4] = 864, C[5] = 4116, C[6] = 19656, C[7] = 9 4380, pqrs[0] = -12, pqrs[1] = 49, pqrs[2] = -78, pqrs[3] = 40, Found: 1 Found: 2 Found: 4 Found: 5 C[1] = 15, C[2] = 407, C[3] = 9507, C[4] = 215951, C[5] = 4861515, C[6] = 108820 727, C[7] = 2424698067, pqrs[0] = -53, pqrs[1] = 980, pqrs[2] = -7396, pqrs[3] = 18480, Found: 5 Found: 12 Found: 14 Found: 22 C[1] = 486, C[2] = 189424, C[3] = 75861486, C[4] = 31342069984, C[5] = 130971109 69326, C[6] = 5492487308851024, C[7] = 2305818940736419566, pqrs[0] = -600, pqrs[1] = 83183, pqrs[2] = -3255216, pqrs[3] = 29549520, Found: 13 Found: 44 Found: 123 Found: 420
