本文介绍了找到2名失踪人数在整数数组有两个缺失值的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

你是怎么做到这一点?该值是无序,但 [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.

根据从@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名失踪人数在整数数组有两个缺失值的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-13 18:02