查找数组中缺少的元素
给定一个大小为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_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
现在假设a，b，x，y是四次多项式的根 P(z) = z^4 + pz^3 + qz^2 + rz + s
现在我们尝试将上面的七个方程变换成四个线性方程p,q,r,s。
例如，如果我们这样做 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 = 0C6 + 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) = 0aP(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是不同的，则是可逆的。
因此，我们必须做到这一点P(a) = P(b) = P(x) = P(y) = 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] = 94380,
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
以上是 查找数组中缺少的元素 的全部内容， 来源链接： utcz.com/qa/399217.html
