查找数组中缺少的元素
假设你有一个大小为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。
arrays有两种可能性：
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等。
现在我们计算七件事：
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 ab -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与Vandermonde矩阵相同的行列式 ，因此是可逆的。
因此，我们必须得到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
第一个循环置换数组，以便如果元素x至少存在一次，那么这些条目中的一个将位于位置A[x] 。
请注意，虽然它有一个嵌套循环，但它仍然在O(N)时间内运行 – 只有当i这样的A[i] != i时才会发生交换，并且每个交换设置至少一个元素使得A[i] == i ，之前的情况并非如此。 这意味着交换的总数（以及while循环体的执行总数）最多为N-1 。
你的解决方案还不错。 这是另一种选择 – 对列表进行排序并迭代检查相邻的数字。 如果存在间隙，请打印其间的所有数字。 如果k是数组的长度而n是要计数的数，我们得到O（k lg k + n）时间，O（1）空间
这有点qwirky因为你的所有数字都是积极的（按问题）。 如果i存在于数组中，我将使位置i-1处的数字变为negetive。
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 [i] – 1] + = k; 在这个循环之后，每个数组元素包含两组信息，最初在数组元素中的数字+ k *（数组中第i个数的出现次数）。
在第二个循环中，你可以通过k对每个位置的数字进行整数除法来找出第i个数的重复次数。 并且在第i个位置的原始数字将是[i]％k;
让我们通过一个例子
A[5] = {1,2,1,3,2};
这里（addfactor）k = 5（数组长度）+ 1 = 6
在fisrt循环数组之后看起来如果原始元素是m并且出现第i个数是O(i)得到的数组元素将是m + k * O(i)这个元素除以（整数）k，你会得到第i个出现elemnent，％k你会得到原始数组。
A = {1 + 6*2, 2 + 6*2, 1 + 6*1, 3+6*0 , 2+6*0 }
A = {13, 14, 7, 3, 2 }
以下是C＃代码（对不起，我的C有点生锈，已经有一段时间了。）可以通过替换Printf和scanfs移植到任何语言。
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 } }
循环每个元素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
在循环结束时，传递每个A [0 ... n-1]。 正元素的索引+ 1是缺失的数字。
因此，如果
y = abs(A[i]) > 0: i + 1 is missing.
在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]; } }
arrays和新arrays一样好。
我们知道我们正在寻找1到N之间的元素创建一个包含1到N的哈希集。
foreach(int i in input) { if(hashset.contains(i)) { hashset.delete(i); } } return "remaining elements in Hashset.";
Hashset中的其余元素是缺少的元素。
As you have given an array of n size and find the missing number when it's in a sequence.
#include main() { print("value of n"); scan("%d",&n); print("enter the elements"); for(i=0;i
It would find the missing when its in sequence only.
一个示例代码片段，用于查找缺少的元素，而不对下面的数组进行排序：
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; } }
此代码适用于从0到N的一系列数字。