Java 在具有两个缺失值的整数数组中查找 2 个缺失的数字

Find 2 missing numbers in an array of integers with two missing values

提问by ordinary

How do you do this? The values are unsorted but are of [1..n]Example array [3,1,2,5,7,8]. Answer: 4, 6

你怎么做到这一点？这些值未排序，但属于[1..n]Example array [3,1,2,5,7,8]。回答：4, 6

I saw this solution in another similar post, but I do not understand the last step:

我在另一个类似的帖子中看到了这个解决方案，但我不明白最后一步：

• Find the sum of the numbers S=a1+...+an.
• Also find the sum of squares T=a12+...+an2.
• You know that the sum should be S'=1+...+n=n(n+1)/2
• You know that the sum of squares should be T'=12+...+n2=n(n+1)(2n+1)/6.
• Now set up the following system of equations x+y=S'-S, x2+y2=T'-T.
• Solve by writing x2+y2=(x+y)2-2xy => xy=((S'-S)2-(T'-T))/2.
• And now the numbers are merely the roots of the quadratic in z: z2-(S'-S)z+((S'-S)2-(T'-T))/2=0.

• 求数字之和 S=a1+...+an。
• 还要求平方和 T=a12+...+an2。
• 你知道总和应该是 S'=1+...+n=n(n+1)/2
• 你知道平方和应该是 T'=12+...+n2=n(n+1)(2n+1)/6。
• 现在建立以下方程组 x+y=S'-S, x2+y2=T'-T。
• 通过编写 x2+y2=(x+y)2-2xy => xy=((S'-S)2-(T'-T))/2 求解。
• 现在这些数字只是 z 中二次方的根：z2-(S'-S)z+((S'-S)2-(T'-T))/2=0。

What is the explanation for setting up that quadratic equation in the final step with z as the unknown? What's the intuition behind that being the solution to this problem?

在最后一步以 z 为未知数建立二次方程的解释是什么？作为这个问题的解决方案背后的直觉是什么？

回答by slider

Let x and y be the roots of a quadratic equation.

设 x 和 y 是二次方程的根。

• Sum of the roots, SUM= x + y
• Product of the roots, PRODUCT= x * y

• 根的总和，SUM= x + y
• 根的乘积，PRODUCT= x * y

If we know the sum and the product, we can reconstruct the quadratic equation as:

如果我们知道和和乘积，我们可以将二次方程重构为：

z^2 - (SUM)z + (PRODUCT) = 0

In the algorithm you mentioned, we find the sum and the product, and from that, we reconstruct the quadratic equation using the above formula.

在你提到的算法中，我们找到了和和乘积，然后我们用上面的公式重建了二次方程。

If you are interested in a detailed derivation, here is a reference. Read "Reconstruction of the quadratic equation from the sum and product of roots".

如果你对详细的推导感兴趣，这里是一个参考。阅读“从根的和和乘积重建二次方程”。

回答by Trying

This method is not advisable as it suffers from integeroverflow problems. So use XORmethod to find the two numbers, which is highly performant. If you are interested i can explain.

这种方法不可取，因为它integer存在溢出问题。所以使用XOR方法来找到两个数字，这是高性能的。如果你有兴趣，我可以解释。

As per the request from @ordinarybelow, i am explaining the algorithm:

根据下面@ordinary的请求，我正在解释算法：

EDIT

编辑

Suppose the maximum element of the array a[]is Bi.e. suppose a[]={1,2,4}and here 3and 5are not present in a[] so max element is B=5.

假设数组的最大元素a[]是Bie 假设a[]={1,2,4}和 here3并且5不存在于 a[] 中，所以最大元素是B=5。

• xorall the elements of the array ato X
• xorall the elements from 1 to Bto x
• find the left most bit set of xby x = x &(~(x-1));
• Now if a[i] ^ x == xthan xora[i]to pelse xorwith q
• Now for all kfrom 1 to Bif k ^ x == xthan xorwith pelse xorwith q
• Now print pand q

• xor该阵列的所有元件a以X
• xor所有元素从1到B至x
• 找到xby的最左边的位集x = x &(~(x-1));
• 现在，如果a[i] ^ x == x不是xora[i]到p别的xor用q
• 现在，所有k从1到B，如果k ^ x == x不是xor与p其他xor有q
• 现在打印p和q

proof:

证明：

Let a = {1,2,4}and Bis 5 i.e. from 1 to 5 the missing numbers are 3 and 5

让a = {1,2,4}和B是 5 即从 1 到 5 缺少的数字是 3 和 5

Once we XORelements of aand the numbers from 1 to 5 we left with XORof 3 and 5 i.e. x.

一旦我们从 1 到 5 的XOR元素a和数字，我们就剩下XOR3 和 5，即x。

Now when we find the leftmost bit set of xit is nothing but the left most different bit among 3 and 5. (3--> 011, 5 --> 101and x = 010where x = 3 ^ 5)

现在，当我们发现它的最左边的位集x只是 3 和 5 之间最左边的不同位时。 ( 3--> 011, 5 --> 101and x = 010where x = 3 ^ 5)

After this we are trying to divide into two groups according to the bit set of xso the two groups will be:

在此之后，我们尝试根据 的位集x分为两组，因此两组将是：

p = 2 , 2 , 3 (all has the 2nd last bit set)

q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)

if we XORthe elements of pamong themselves we will find 3and similarly if we xorall the elements of qamong themselves than we will get 5. Hence the answer.

如果我们之间XOR的元素p我们会找到3，同样如果我们xor所有的元素q之间比我们会得到 5。因此答案。

code in java

java中的代码

public void findNumbers(int[] a, int B){
    int x=0;
    for(int i=0; i<a.length;i++){
        x=x^a[i];
    }
    for(int i=1;i<=B;i++){
        x=x^i;
    }
    x = x &(~(x-1));
    int p=0, q=0;
    for(int i=0;i<a.length;i++){
        if((a[i] & x) == x){
            p=p^a[i];
        }
        else{
            q=q^a[i];
        }   
    }
    for(int i=1;i<=B;i++){
        if((i & x) == x){
            p=p^i;
        }
        else{
            q=q^i;
        }
    }

    System.out.println("p: "+p+" : "+q);
}

回答by Ben Voigt

Starting with

从...开始

x+y == SUM
xy == PRODUCT

There are two cases. If PRODUCT is zero, then one number is 0and the other is SUM. Otherwise both are non-zero; we can multiply the first equation by xwithout changing the equality:

有两种情况。如果 PRODUCT 为零，则一个数字是0，另一个是SUM。否则两者都不为零；我们可以在x不改变等式的情况下乘以第一个等式：

x*x + xy == x*SUM

Substitute the second equation:

代入第二个方程：

x*x + PRODUCT = x*SUM

and rearrange in the usual form

并以通常的形式重新排列

x*x - x*SUM + PRODUCT = 0

So that

以便

x = SUM/2 + sqrt(SUM*SUM - 4*PRODUCT)/2
y = SUM/2 - sqrt(SUM*SUM - 4*PRODUCT)/2

回答by user1789685

Below is the generic answer in java code for any number of missing numbers in a given array
//assumes that there are no duplicates
a = [1,2,3,4,5]
b = [1,2,5]
a-b=[3,4]

public list<integer> find(int[] input){
  int[] a= new int[] {1,2,3,4,5};//create a new array without missing numbers
  List<Integer> l = new ArrayList<Integer>();//list for missing numbers
  Map<Integer,Integer> m = new HashMap<Integer>();

  //populate a hashmap with the elements in the new array
  for(int i=0;i<input.length;i++){  
   m.put(input[i], 1);
  }
//loop through the given input array and check for missing numbers
 for(int i=0;i<a.length;i++){
  if (!m.contains(input[i]))
   l.add(input[i]);
}
 return l;
}

回答by OhadM

Java implementation:(Based on @Ben Voigt)

Java 实现：（基于@Ben Voigt）

BigInteger fact=1;
int sum=0;
int prod=1;
int x,y; // The 2 missing numbers
int n=a.length;
int max=MIN_VALUE;

for (int i=0; i<a.length;i++){
  sum+=a[i]; //sums the existing numbers
  prod*=a[i]; //product the existing numbers
  if (max<a[i]) //searches for the biggest number in the array
     max=a[i];
}

while(max!=1){ //factorial for the maximum number
     fact*=max;
     max--;
}
sum=(n*(n+1))/2 - sum; //the sum of the 2 missing numbers
prod=fact/prod; //the product of the 2 missing numbers

x=sum/2 + Math.sqrt(sum*sum - 4*prod)/2;
y=sum/2 - Math.sqrt(sum*sum - 4*prod)/2;

回答by Manik Gupta

I have an algorithm for above problem.

我有上述问题的算法。

Suppose

认为

Actual Series: 1 2 3 4 5 6          a:sum=21 product= 720
Missing Number series: 1 * 3 4 * 6  b:sum=14 product= 72

a+b=21-14= 7 , ab=720/72=10

Now we need to find a-b= sqrt[(a+b)^2 -4ab].

现在我们需要找到a-b= sqrt[(a+b)^2 -4ab].

If you calculate:

如果计算：

a-b= 3

Now

现在

a+b=7
a-b=3

Add both equations:

将两个方程相加：

2a=10, a=5

then b=7-5=2so, 2and 5are missing.

然后就b=7-5=2这样了，2而且5都不见了。

回答by Shivam Sharda

I hope this program is useful to you all, i took the limit till 10 it can be done the same way, just use n as the limit and perform the same operations.

我希望这个程序对大家有用，我把限制到 10 它可以用同样的方式完成，只需使用 n 作为限制并执行相同的操作。

#include <iostream>
#include<math.h>

using namespace std;

int main()
{
    int i,x[100],sum1=0,sum2=0,prod1=1,prod2=1,k,j,p=0;
    cout<<"Enter 8 elements less than 10, they should be non recurring"<<endl;
    for(i=0;i<8;i++)
    {
        cin>>x[i];
    }
    sum1=((10)*(11))/2;
    for(i=0;i<8;i++)
    {
        sum2+=x[i];
    }
    k=sum1-sum2;
    for(i=1;i<10;i++)
    {
        prod1=prod1*i;
    }
    for(i=0;i<8;i++)
    {
        prod2=prod2*x[i];
    }
    j=prod1/prod2;
    p=sqrt((k*k)-(4*j));
    cout<<"One missing no:"<<p/2<<endl;
    cout<<"Second missing no:"<<k-p/2<<endl;


}

回答by Alok Singh

#include <stdio.h>
#include <math.h>

/*
    the sum should be 1+...+n = n(n+1)/2
    the sum of squares should be 1^2+...+n^2 = n(n+1)(2n+1)/6.
*/

void find_missing_2_numbers(int *arr, int n);

int main()
{
    int arr[] = {3,7,1,6,8,5};

    find_missing_2_numbers(arr, 8);

    return 0;
}

void find_missing_2_numbers(int *arr, int n)
{

    int i, size, a, b, sum, sum_of_sqr, a_p_b, as_p_bs, a_i_b, a_m_b;
    size = n - 2;

    sum = 0;
    sum_of_sqr = 0;
    for (i = 0; i < size; i++)
    {
        sum += arr[i];
        sum_of_sqr += (arr[i] * arr[i]);
    }

    a_p_b = (n*(n+1))/2 - sum;
    as_p_bs = (n*(n+1)*(2 * n + 1))/6 - sum_of_sqr;
    a_i_b = ((a_p_b * a_p_b) - as_p_bs ) / 2;
    a_m_b = (int) sqrt((a_p_b * a_p_b) - 4 * a_i_b);
    a = (a_p_b + a_m_b) / 2;
    b = a_p_b - a;

    printf ("A: %d, B: %d\n", a, b);
}

回答by Manash Ranjan Dakua

public class MissingNumber{

static int[] array = { 1, 3, 5 };

public static void getMissingNumber() {

for (int i = 0; i < array.length; i++)
    System.out.println(array[i] + " ");

System.out.println("The Missing Number is:");
 int j = 0;
for (int i = 1; i <= 5; i++) {
    if (j < array.length && i == array[j])
    j++;
    else
    System.out.println(i + " ");
}

}
public static void main(String[] args) {
getMissingNumber();
}

}

}

回答by Frank59

Code sample(Java) for @slider answer

@slider 答案的代码示例（Java）

 /**
     * get 2 missed numbers from randomly shuffled array of unique elements from [1,n]
     *
     * @param array - shuffled array of unique elements from [1,n], but 2 random elements was missed. len = n-2
     * @return array with 2 missed elements
     */
    public static int[] getMissedNumbers(int[] array) {

        int sum = 0;
        int fullSum = 0;
        int fullProduct = 1;
        int product = 1;
        for (int i = 0; i < array.length + 2; i++) {
            int currNaturalNumber = i + 1;
            fullSum = fullSum + currNaturalNumber;
            fullProduct = fullProduct * currNaturalNumber;

            if (i < array.length) {
                sum = sum + array[i];
                product = product * array[i];
            }
        }

        int missedSum = fullSum - sum; //firstMissedNum + secondMissedNum
        int missedProduct = fullProduct / product; //firstMissedNum * secondMissedNum

        //ax*x + bx + c = 0
        //x = (-b +- sqrt(b*b - 4*a*c))/2*a
        // -b = missedSum , c = missedProduct, a = 1
        Double firstMissedNum = (missedSum + Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
        Double secondMissedNum = (missedSum - Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
        return new int[]{firstMissedNum.intValue(), secondMissedNum.intValue()};
    }

and simple arrays generator for tests

和用于测试的简单数组生成器

  public static Map.Entry<int[], int[]> generateArray(int maxN, int missedNumbersCount) {
        int[] initialArr = new int[maxN];
        for (int i = 0; i < maxN; i++) {
            initialArr[i] = i + 1;
        }
        shuffleArray(initialArr);
        int[] skippedNumbers = Arrays.copyOfRange(initialArr, maxN - missedNumbersCount, maxN);
        int[] arrayWithoutSkippedNumbers = Arrays.copyOf(initialArr, maxN - missedNumbersCount);
        return new AbstractMap.SimpleEntry<>(arrayWithoutSkippedNumbers, skippedNumbers);

    }

    private static void shuffleArray(int[] ar) {
        Random rnd = ThreadLocalRandom.current();
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }