在数组中查找丢失的元素。

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.

给定数组A[1。n)大小n，它包含了集合{1..n}中的元素。但是，丢失了两个元素(可能重复了两个数组元素)。找到丢失的元素。

Eg if n=5, A may be A[5] = {1,2,1,3,2}; and so the missing elements are {4,5}

如果n=5，则A可以是[5]= {1,2,1,3,2};所以缺失的元素是{4,5}

The approach I used was:

我使用的方法是:

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));  
}  

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(n)我觉得这是一个非常幼稚和低效的代码。所以你能提供一个更好的，更好的空间和时间复杂度的algo。

9 个解决方案

#1

Theoretically,

从理论上讲,

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.

在O(1)空间中(在RAM模型中，即O(1) words)和O(n)时间，甚至使用一个只读数组都是可行的。

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.

警告:有一些数学的长文章。如果您只对代码感兴趣，而不是对算法/证明感兴趣，请跳到代码部分。不过，您需要阅读算法部分的一些部分才能理解代码。

---

Algorithm

算法

Assume the missing numbers are x and y.

假设丢失的数是x和y。

There are two possibilities for the array:

数组有两种可能:

1) One number is repeated three times, and the remaining numbers in the array appear exactly once.

1)一个数字重复三次，而数组中剩余的数字只出现一次。

For this case, the bucketed XOR trick will work.

在这种情况下，使用的XOR技巧将起作用。

Do a XOR of all elements of the array with 1,2,...,n.

用1、2、…、n来做一个数组的所有元素的XOR。

You end up with z = x XOR y.

最后得到z = x x y。

There is at least one bit of z which is non-zero.

至少有一点z是非零的。

Now differentiating the elements of the array based on that bit (two buckets) do a XOR pass through the array again.

现在根据这个位(两个bucket)来区分数组的元素，然后再进行一次XOR遍历。

You will end up with x and y.

最后得到x和y。

Once you have the x and y, you can confirm if these are indeed the missing elements.

一旦你有了x和y，你就可以确定这些是不是缺失的元素。

If it so happens that the confirmation step fails, then we must have the second case:

如果确认步骤失败，那么我们必须有第二个案例:

2) Two elements repeated exactly twice and the rest appearing exactly once.

2)两种元素重复重复一遍，其余的重复出现一次。

Let the two repeated elements be a and b (x and y are the missing ones).

让两个重复的元素为a和b (x和y是缺失的元素)。

Warning: Math ahead.

警告:数学。

Let S_k = 1^k + 2^k + .. + n^k

让S_k = 1 ^ k + 2 ^ k + . .+ n ^ k

For instance S_1 = n(n+1)/2, S_2 = n(n+1)(2n+1)/6 etc.

例如S_1 = n(n + 1)/ 2,S_2 = n(n + 1)(2 n + 1)/ 6等。

Now we compute seven things:

现在我们计算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

Note, we can use O(1) words (intsead of one) to deal with the overflow issues. (I estimate 8-10 words will be enough).

注意，我们可以使用O(1)单词(intof one)来处理溢出问题。(我估计8-10个字就够了)。

Let Ci = T_i - S_i

让Ci = T_i - S_i。

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

现在,假设a,b,x,y是第四多项式的根P(z)= z ^ 4 + pz ^ 3 +求^ 2 + rz + s

Now we try to transform the above seven equations into four linear equations in p,q,r,s.

现在我们试着把上面的7个方程变成4个线性方程，p,q,r,s。

For instance, if we do 4th Eqn + p * 3rd Eqn + q* 2nd equation + r* 1st equation

例如，如果我们做4个Eqn + p * 3 Eqn + q* 2方程+ r* 1方程。

we get

我们得到了

C4 + p*C3 + q*C2 + r*C1 = 0

C4 + p*C3 + q*C2 + r*C1 = 0。

Similarly we get

同样我们得到

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

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 q r s到上面的方程组。

Consider P(z) = z^4 + pz^3 + qz^2 + rz + s.

考虑P(z)= z ^ 4 + pz ^ 3 +求^ 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

Now the matrix

现在的矩阵

   1   1  -1 -1
   a   b   -x   -y
   a^2 b^2 -x^2 -y^2
   a^3 b^3 -x^3 -y^3

has the same determinant as the Vandermonde matrix and thus is invertible, if a,b,x,y are distinct.

与范德蒙矩阵有相同的行列式因此是可逆的，如果a b x y是不同的。

Thus we must have that P(a) = P(b) = P(x) = P(y) = 0.

因此，P(a) = P(b) = P(x) = P(y) = 0。

Now check which of 1,2,3,...,n are roots of x^4 + px^3 + qx^2 + rx + s = 0.

现在检查1 2 3，…,n根x ^ ^ 3 + 4 + px qx ^ 2 + rx + s = 0。

Thus this is a linear time constant space algorithm.

因此这是一个线性时间常数空间算法。

---

Code

代码

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).

我写了下面的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;
        }
    }
}

The output is

输出是

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

#2

As @j_random_hacker pointed out, this is quite similar to Finding duplicates in O(n) time and O(1) space, and an adaptation of my answer there works here too. In pseudo-code:

正如@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

The first loop permutes the array so that if element x is present at least once, then one of those entries will be at position A[x].

第一个循环遍历数组，以便如果元素x至少出现一次，那么其中一个条目将处于位置A[x]。

Note that although it has a nested loop, it still runs in O(N) time - a swap only occurs if there is an i such that A[i] != i, and each swap sets at least one element such that A[i] == i, where that wasn't true before. This means that the total number of swaps (and thus the total number of executions of the while loop body) is at most N-1.

注意，虽然它有一个嵌套循环，但它仍然在O(N)时间内运行——只有当i (i) != i时才会发生交换，并且每个交换器至少设置一个元素，例如i，在这里，这不是正确的。这意味着交换的总数(也就是while循环体的执行总数)最多为N-1。

#3

Your solution isn't bad. Here's an alternative - Sort the list and iterate through it checking adjacent numbers. When there is a gap, print all the numbers in between. If k is the length of the array and n is the number to count to, we get O(k lg k + n) time, O(1) space

你的解决方案并不坏。这是一个可选的排序列表，并通过它检查相邻的数字。当有间隙时，打印出中间的所有数字。如果k是数组的长度n是计数的个数，我们得到O(k + n)时间，O(1)空间。

#4

This is bit qwirky As all your numbers are positive (by problem). I ll make the number at position i-1 a negetive if i is present in array.

这是有点qwirky，因为所有的数字都是正的(通过问题)。如果我出现在数组中，我将使位置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);  
}  

Complexity O(n), no auxiliary array user, but destroys the input array.

复杂度O(n)，没有辅助数组用户，但破坏了输入数组。

#5

Following is one of the approaches to identify all missing numbers when an array is known to contain only lumbers between 1 to n inclusive, without using any additional space. Time complexity is O(n).

下面是一种识别所有丢失的数字的方法之一，当已知一个数组只包含1到n个包含的块时，不使用任何额外的空间。时间复杂度是O(n)。

Lets take a smallest number k such that it is not supposed to be in array therfore k = n+1 (lets call it an add factor).

让我们取一个最小的k，这样它就不应该出现在数组中，所以k = n+1(我们称之为添加因子)。

first loop through each array and for every a[i] we will update a[a[i] - 1] += k; after this loop every array element contains two sets of information the number which was originally in the array element + k * (number of occurances of ith number in the array).

第一个循环遍历每个数组，每一个[i]我们将更新一个[i] - 1] += k;在此循环之后，每个数组元素包含两组信息，这些信息最初是数组元素+ k *(数组中第i个数字的出现次数)。

in the second loop you could find out how many repetations of ith number by doing an integer division of the number at each location by k. And original number at ith location would be a[i] % k;

在第二个循环中，你可以通过在每个位置用k来做一个整数除法来找出第i个数字的多少次重复，第i个位置的原始数字是一个[i] % k;

Lets work through an example

让我们来看一个例子。

A[5] = {1,2,1,3,2};

[5]= { 1、2、1、3、2 };

here (addfactor) k = 5 (array length) + 1 = 6

这里(addfactor) k = 5(数组长度)+ 1 = 6。

After fisrt loop array would look like if original element is m and occurances of ith number is O(i) resulting array element would be m + k * O(i) this element divide(integer) by k you'll get occurances of ith elemnent, and %k you'd get original array.

如果第一个元素是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 }

A = { 1 + 6 * 2,2 + 6 * 2,1 + 6 * 1,3 + 6 * 0,2 + 6 * 0 } = { 13、14、7、3、2 }

Following is C# code which (I'm sorry, my C is little rusty its been a while.) could be ported to any language just by replacing Printf & scanfs.

下面是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
        }
    }

#6

Cycle each element 0...n-1.

每个元素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

At the end of the cycle, pass each A[0...n-1]. The index of the positive elements + 1 is the missing numbers.

在循环结束时，传递每一个A[0…n-1]。正元素的指数+ 1是缺失的数。

So if

因此,如果

y = abs(A[i]) > 0: i + 1 is missing.

In C#

在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];
    }
}

And the array is as good as new.

这个数组就像新的一样。

#7

As we know we are looking for elements between 1 to N Create a Hash set containing 1 to N.

正如我们所知道的，我们正在寻找1到N之间的元素，创建一个包含1到N的散列集合。

foreach(int i in input)
{
   if(hashset.contains(i))
   {
      hashset.delete(i);
   }
}

return "remaining elements in Hashset.";

The remaining elements in Hashset are the missing elements.

Hashset中的其余元素是缺失的元素。

#8

As you have given an array of n size and find the missing number when it's in a sequence.

当你给定一个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]);
}
}

It would find the missing when its in sequence only.

它只会在序列中找到缺失的部分。

#9

A sample code snippet for finding the missing elements without sorting the array below:

一个示例代码片段，用于查找缺少的元素，而无需对下面的数组进行排序:

     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;
        }
     }

This code works for a series of numbers from 0 to N.

该代码适用于从0到N的一系列数字。