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

Question

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

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

• 找到数字的总和S = a1 + ... + an.
• 还可以找到平方和T =a1²+ ... +an².
• 你知道总和应该是S'= 1 + ... + n = n(n + 1)/ 2
• 你知道平方和应该是T'=1²+ ... +n²= n(n + 1)(2n + 1)/ 6.
• 现在建立以下方程组x + y = S'-S,x²+ y2 = T'-T.
• 通过写x²+ y2 =(x + y)²-2xy => xy =((S'-S)²-(T'-T))/ 2来求解.
• 现在这些数字仅仅是z中的二次曲线的根:z 2 - (S'-S)z +((S'-S)²-(T'-T))/ 2 = 0.

在z为未知的最后一步中设置二次方程的解释是什么？解决这个问题背后的直觉是什么？

Answer 1

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

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

编辑

假设数组的最大元素a[]是B假定的a[]={1,2,4},这里3并且5不存在于[]中,因此最大元素是B=5.

• xor该阵列的所有元件a以X
• xor所有元素从1 B到x
• 找到最左边位组x由x = x &(~(x-1));
• 现在,如果a[i] ^ x == x不是xor a[i]以p其他xor方式q
• 现在为所有人k从1到Bif而k ^ x == x不是xor与p其他人xor一起q
• 现在打印p和q

证明:

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

一旦我们的XOR元素a和数字从1到5,我们留下XOR3和5即x.

现在,当我们发现的最左边位设置x它只不过是最左边的不同位之间3和5( 3--> 011,5 --> 101并x = 010在那里x = 3 ^ 5)

在此之后,我们尝试根据位集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)

如果我们他们之间XOR的元素p我们会发现3,同样地,如果我们xor所有的元素,q我们将得到5.因此答案.

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

Answer 2

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

• 根总和,SUM= x + y
• 根的产物,PRODUCT= x*y

如果我们知道总和和乘积,我们可以将二次方程重建为:

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

在你提到的算法中,我们找到总和和乘积,然后我们使用上面的公式重建二次方程.

如果您对详细的推导感兴趣,请参考以下内容.阅读"从根的总和和乘积重构二次方程".

Answer 3

从...开始

x+y == SUM
xy == PRODUCT

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

x*x + xy == x*SUM

代入第二个方程：

x*x + PRODUCT = x*SUM

并以通常的形式重新排列

x*x - x*SUM + PRODUCT = 0

以便

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

Answer 4

我有一个针对上述问题的算法.

假设

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

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

如果你计算:

a-b= 3

现在

a+b=7
a-b=3

添加两个方程式:

2a=10, a=5

那么b=7-5=2,2并且5失踪了.