寻找丢失的数组中的元素组中、元素
鉴于你有一个数组大小为n A [1..1]，它包含了从集合{1..N}元素。但是，有两个要素是缺少，（也许两个数组元素被重复）。查找缺少的元素。
Given you have an array A[1..n] of size n, it contains elements from the set {1..n}. However, two of the elements are missing, (and perhaps two of the array elements are repeated). Find the missing elements.
如：N = 5，A可以是A [5] = {1,2,1,3,2};所以缺少的元素{4,5}
Eg if n=5, A may be A[5] = {1,2,1,3,2}; and so the missing elements are {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）。我觉得这是一个非常kiddish和低效code。所以，请你提供更好的算法中具有更好的空间和时间复杂度。
the space complexity comes to O(n). I feel this is a very kiddish and inefficient code. So could you please provide a better algo with better space and time complexity.
推荐答案
从理论上讲，
这是可以做到在O（1）空间（RAM中的模型，即O（1）的话）和O（n）的时间，即使只读数组。
It is possible to do in O(1) space (in RAM model, i.e. O(1) words) and O(n) time even with a read-only array.
警告：长时间使用后的一些数学。如果你只关心code，而不是算法/证明，跳到code部分。您将需要阅读的算法部分的某些部分，了解code，虽然。
Warning: Long post with some mathematics. If you are only interested in the code and not the algorithm/proof, skip to the code section. You would need to read some parts of the algorithm section to understand the code, though.
算法
假设丢失号码是x和y
Assume the missing numbers are x and y.
有两种可能的数组：
1）一数量被重复三次，并且阵列中的剩余的数字中出现一次。
1) One number is repeated three times, and the remaining numbers in the array appear exactly once.
有关这种情况下，分时段的XOR招会奏效。
For this case, the bucketed XOR trick will work.
执行数组中的所有元素的异或1,2，...，N。
Do a XOR of all elements of the array with 1,2,...,n.
您结束了Z = XOR年。
You end up with z = x XOR y.
有是z的至少一个位，该位是非零
There is at least one bit of z which is non-zero.
现在区分基于该比特数组的元素（两个桶）做一个异或穿过该阵列再次
Now differentiating the elements of the array based on that bit (two buckets) do a XOR pass through the array again.
您将结束与x和y。
一旦你的x和y，可以确认，如果这些确实缺少的元素。
Once you have the x and y, you can confirm if these are indeed the missing elements.
如果恰巧确认步骤失败，那么我们就必须有第二种情况：
If it so happens that the confirmation step fails, then we must have the second case:
2）的两个元素正好重复两次，其余的出现一次。
2) Two elements repeated exactly twice and the rest appearing exactly once.
让两个重复的元素是a和b（x和y是缺少的）。
Let the two repeated elements be a and b (x and y are the missing ones).
警告：数学提前
让 S_k = 1 ^ K + 2 ^ K + ... + N ^氏/ code>
Let S_k = 1^k + 2^k + .. + n^k
例如 S_1 = N（N + 1）/ 2 ， S_2 = N（N + 1）（2N + 1）/ 6 等。
现在我们计算的 7 的事情：
Now we compute seven things:
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）字（一intsead）来处理溢出的问题。 （我估计8-10的话就足够了）。
Note, we can use O(1) words (intsead of one) to deal with the overflow issues. (I estimate 8-10 words will be enough).
让 CI = T_i - S_I
现在假设A，B，X，Y是第4次多项式 P（Z）= Z ^ 4 + PZ ^ 3 + QZ ^ 2 + RZ + S的根源
Now assume that a,b,x,y are the roots of the 4th degree polynomial P(z) = z^4 + pz^3 + qz^2 + rz + s
现在，我们尝试了上述七种方程转化为四个线性方程 P，Q，R，S 。
Now we try to transform the above seven equations into four linear equations in p,q,r,s.
举例来说，如果我们这样做 4方程+ P * 3方程+ Q *第二方程+ R * 1号公式
For instance, if we do 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 四个线性方程可以通过线性代数技术，如高斯消元。
These are four linear equations in p,q,r,s which can be solved by Linear Algebra techniques like Gaussian Elimination.
注意 P，Q，R，S 将是有理数，因此只能用整数运算计算。
Note that p,q,r,s will be rationals and so can be computed only with integer arithmetic.
现在假设我们有一个解决方案 P，Q，R，S 上面的方程组。
Now suppose we are given a solution p,q,r,s to the above set of equations.
考虑 P（Z）= Z ^ 4 + PZ ^ 3 + QZ ^ 2 + RZ + S 。
什么是上述公式的意思是基本上
What the above equations are saying is basically
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 是不同的。
has the same determinant as the Vandermonde matrix and thus is invertible, if a,b,x,y are distinct.
因此，我们必须有一个 P（A）= P（B）= P（X）= P（Y）= 0 。
Thus we must have that P(a) = P(b) = P(x) = P(y) = 0.
现在检查其中 1,2,3，...，N 是根X ^ 4 + PX ^ 3 + QX ^ 2 + RX + S = 0 。
因此，这是一个线性的时间常数空间算法。
Thus this is a linear time constant space algorithm.
code
我写了下面的C＃（.NET 4.0）code和它似乎工作的几样我想...（注：我没有刻意迎合区分1以上）。
I wrote the following C# (.Net 4.0) code and it seems to work for the few samples I tried... (Note: I didn't bother catering to case 1 above).
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
