找到2名失踪人数在整数数组有两个缺失值 [英] Find 2 missing numbers in an array of integers with two missing values

问题描述

你是怎么做到这一点？该值是无序，但 [1..1] 例阵列 [3,1,2,5,7,8] 。答： 4，6

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

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

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=a1*a1+...+an*an.
You know that the sum should be S'=1+...+n=n(n+1)/2
You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6.
Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T.
Solve by writing x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2. 
And now the numbers are merely the roots of the quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.

什么是设置的解释在以Z为未知的最后一步二次方程？那是什么是解决这个问题呢？

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?

推荐答案

这个方法是不可取的，因为它从整数溢出问题受到影响。所以，使用 XOR 方法查找两个数字，这是非常高性能的​​。如果你有兴趣，我可以解释的。

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

根据从<一个请求href="http://stackoverflow.com/questions/20026243/find-2-missing-numbers-in-an-array-of-integers-with-two-missing-values/20026969#comment29823492_20026969">@ordinary下面，我解释算法：

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

修改

假设数组的最大元素 A [] 是 B 即假设 A [] = {1,2,4} 这里 3 和 5 不present在[]所以最大元素是 B = 5 。

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

• XOR 阵列中的所有元素 A 到 X
• XOR 1的所有元素 B 到 X
• 找到最左边位组 X 按 X = X及（〜（X-1））;
• 现在，如果 A [1] ^ X = = X 比 XOR A [我] 到 P 其他 XOR 与①
• 现在，所有 K 1至 B 如果 K ^ x的== x 比 XOR 与 P 其他 XOR 与①
• 现在，打印 P 和①

• xor all the elements of the array a to X
• xor all the elements from 1 to B to x
• find the left most bit set of x by x = x &(~(x-1));
• Now if a[i] ^ x == x than xor a[i] to p else xor with q
• Now for all k from 1 to B if k ^ x == x than xor with p else xor with q
• Now print p and q

证明：

让 A = {1,2,4} 和 B 5，即从1到5的缺失号是3和5

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

在我们 XOR 的元素 A 我们留下的数字从1到5 XOR 3个和5个，即 X 。

Once we XOR elements of a and the numbers from 1 to 5 we left with XOR of 3 and 5 i.e. x.

现在，当我们找到了最左边位组 X 这只不过是最左边的不同位之间3和5（3-- <$ C C $> ＆GT; 011 ， 5 - ＆GT; 101 和 X = 010 ，其中 X = 3 ^ 5 ）

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

在此我们试图根据位组 X 使两大集团将分为两组：

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

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

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

如果我们 XOR 的 P 它们之间的元素，我们会发现 3 ，同样，如果我们 XOR 的①所有彼此之间的内容比我们会得到5。 因此，问题的答案。

if we XOR the elements of p among themselves we will find 3 and similarly if we xor all the elements of q among themselves than we will get 5. Hence the answer.

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

这篇关于找到2名失踪人数在整数数组有两个缺失值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！