假设你有一个大小为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)。我感觉这是非常幼稚和低效的代码。你能否提供一个更好的算法，具有更好的时间和空间复杂度。
警告：本文较长，包含一些数学内容。如果您只对代码而不是算法/证明感兴趣，请跳到代码部分。但是，您需要阅读算法部分的某些部分才能理解代码。
算法
假设缺失的数字是x和y。
数组有两种可能性：
1）一个数字重复三次，数组中其余数字仅出现一次。
对于这种情况，桶式XOR技巧将起作用。
使用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 等等。
现在我们计算 七个 东西：
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)个单词（而不是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四个线性方程。
例如，如果我们执行第四个方程+ p * 第三个方程+ q * 第二个方程+ r * 第一个方程
我们得到
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不同，则具有与范德蒙矩阵相同的行列式，因此是可逆的。
因此，我们必须有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
1,1,2,2,3：
c1 = 6 C2 = 36 c3 = 180 C4 = 864 C5 = 4116 C6 = 19656 C7 = 94380 解决方案为 p=-12, q= 49, r = -78, s= 40。相应的多项式是(z-1)(z-2)(z-4)(z-5)。 - Aryabhatta正如 @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
x 至少出现一次，则其中一个条目将位于位置 A[x]。O(N) 时间内运行 - 仅当存在一个 i 使得 A[i] != i 时才会发生交换，并且每个交换都至少设置一个元素，使得 A[i] == i，这在之前不是真的。这意味着交换的总数（因此执行 while 循环体的总次数）最多为 N-1。你的解决方案不错。这里有一个替代方案 - 对列表进行排序，然后遍历并检查相邻数字。当出现间隙时，打印中间所有的数字。如果k是数组的长度，n是要计数的数字，则我们得到O(k lg k + n)时间复杂度，O(1)空间复杂度。
public static void series(int[] arr) {
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i + 1) {
int jump = arr[arr[i] - 1];
if (jump == arr[i]) {
break;
}
arr[arr[i] - 1] = arr[i];
arr[i] = jump;
}
}
System.out.println("Missing number is ");
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i + 1) {
System.out.println(i + 1);
} else {
arr[i] = -1;
}
}
while ( arr[i] != i + 1 )替换为while ( arr[arr[i] - 1] != arr[i] )，然后摆脱if (jump == arr[i])条件，直接执行swap ( arr[arr[i] - 1], arr[i] )。 - Chandan Hegde这有点奇怪，因为所有的数字都是正数（由于问题）。如果i在数组中出现，我会将位置i-1上的数字变成负数。
int i;
for(i = 0; i < n; i++) {
A[abs(A[i])-1] = -1*abs(A[abs(A[i])-1]);
}
for(i = 0; i < n; i++) {
if(A[i]>0) {
printf("missing: %d", i+1);
}
时间复杂度为O(n)，不使用辅助数组，但会破坏输入的数组。
以下是一种方法，用于在已知数组仅包含介于1到n之间的数字时，识别所有缺失的数字，而不使用任何额外的空间。时间复杂度为O(n)。
让我们取一个最小的数字k，使得它不应该在数组中，因此k = n + 1（我们称之为添加因子）。
首先循环遍历每个数组，对于每个a[i]，我们将更新a[a[i]-1] += k; 在这个循环后，每个数组元素都包含两组信息：原来在数组元素中的数字+k *（数组中第i个数字出现的次数）。
在第二个循环中，您可以通过在每个位置处对数字进行整数除法来找出第i个数字的重复次数。第i个位置的原始数字将是a[i]％k;
让我们通过一个例子来说明
A[5] = {1,2,1,3,2};
这里（添加因子）k = 5（数组长度）+1 = 6
第一个循环后，如果原始元素为m，第i个数字的出现次数为O(i)，则结果数组元素将为m + k * O(i)。将该元素除以k（整数），您将得到第i个元素的出现次数，%k将得到原始数组。
A = {1 + 6*2, 2 + 6*2, 1 + 6*1, 3+6*0 , 2+6*0 }
A = {13, 14, 7, 3, 2 }
以下是C#代码，可以通过替换Printf和scanfs来移植到任何语言中（对不起，我的C有点生疏，已经有一段时间了）。
static void Main(string[] args)
{
int[] A = { 1, 2, 1, 3, 2 };
PrintDuplicateAndMissing(A);
Console.ReadLine();
}
static void PrintDuplicateAndMissing(int[] array)
{
int addfactor = array.Length + 1;
for (int i = 0; i < array.Length; i++)
{
array[array[i] - 1] += addfactor; // -1 only if array contains from 1 to n. if it is 0 to n (this -1 is not required)
}
for (int i = 0; i < array.Length; i++)
{
if ( (array[i] / addfactor) == 0 )
Console.WriteLine(string.Format("{0} is missing", i + 1)); // i + 1 only if array is 1 to n, if 0 to n then +1 is not required
array[i] %= addfactor; //restore original content of the array
}
}
我们知道，我们正在寻找1到N之间的元素。创建一个包含1到N的哈希集合。
foreach(int i in input)
{
if(hashset.contains(i))
{
hashset.delete(i);
}
}
return "remaining elements in Hashset.";
Hashset 中剩余的元素是缺失的元素。
循环每个元素0...n-1。
x = abs(A[i]) (with i = 0...n-1);
A[x - 1] can be:
> 0: we haven't checked the element, change its sign to negative:
A[x - 1] = -A[x - 1]
< 0: we already found the same number
y = abs(A[i]) > 0: i + 1 is missing.
In C#
var arr = new[] { 1, 2, 1, 2, 4 };
for (int i = 0; i < arr.Length; i++) {
int x = Math.Abs(arr[i]);
int y = arr[x - 1];
if (y > 0) {
arr[x - 1] = -arr[x - 1];
}
}
for (int i = 0; i < arr.Length; i++) {
int x = arr[i];
if (x > 0) {
Console.WriteLine("Missing {0}", i + 1);
} else {
arr[i] = -arr[i];
}
}
而且数组就像新的一样好。
假设你有一个大小为n的数组，并且需要在其中找到缺失的数字，当它们在一个序列中时。
#include<stdio.h>
main()
{
print("value of n");
scan("%d",&n);
print("enter the elements");
for(i=0;i<n;i++)
scan("%d",&a[i]);
for(i=0;i<n;i++)
{
d1[i]=a[i+1]-a[i];
temp=d1[i];
d[i]=temp;
}
for(i=0;i<n;i++)
{
if(d[i]==d[i+1]
{
c=d[i];
break;
}
}
for(i=0;i<n;i++)
b[i]=a[0]+i*c;
for(i=0;i<n;i++)
{
miss=0;
for(j=0;j<n;j++)
{
if(b[i]!=a[j])
{
miss++;
}
if(miss==n)
print("missing no. %d",b[i]);
}
}
只有在连续时才会找到缺失的元素。
flag[A[i]] = 1;这是不行的！根据您的帖子，每个A[i]的值在 1 到 n 之间；flag[n]是未定义的（flag 的索引从0到n-1）。哦...你试图访问A[0]，但根据您的帖子，它不应该被考虑；而且你没有访问到A[n]（你最后查看的A是A[n-1]）。另一方面，如果A被定义为A[5] = {1, 2, 1, 3, 2}，那么描述中存在不一致性。 - pmg