假设你有一个大小为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).我觉得这是一个非常儿童和低效的代码.那么请你提供一个更好的空间和时间复杂度的更好的算法.
小智 15
从理论上讲,
即使使用只读数组,也可以在O(1)空间(在RAM模型中,即O(1)字)和O(n)时间内完成.
警告:有一些数学的长篇文章.如果您只对代码而不是算法/证据感兴趣,请跳至代码部分.但是,您需要阅读算法部分的某些部分才能理解代码.
算法
假设缺少的数字是x和y.
阵列有两种可能性:
1)一个数字重复三次,数组中的其余数字恰好出现一次.
对于这种情况,分段的XOR技巧将起作用.
用1,2,...,n对数组的所有元素进行异或.
你最终得到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)字(intsead of one)来处理溢出问题.(我估计8-10个单词就足够了).
让 Ci = T_i - S_i
现在假设a,b,x,y是4次多项式的根 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 = 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
具有与Vandermonde矩阵相同的行列式,因此如果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] = 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
正如@j_random_hacker所指出的,这非常类似于在O(n)时间和O(1)空间中查找重复项,并且我的答案也适用于此处.在伪代码中:
for i := 1 to n
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end if
end for
for i := 1 to n
if A[i] != i then
print i
end if
end for
第一个循环置换数组,以便if元素x至少存在一次,那么其中一个条目将处于位置A[x].
请注意,尽管它有一个嵌套循环,但它仍然会O(N)及时运行- 只有在存在i这样的情况时才会发生交换A[i] != i,并且每个交换都设置至少一个元素A[i] == i,以便之前不是这样.这意味着交换的总数(以及while循环体的总执行次数)最多N-1.