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

arrays algorithm math java c++

2022-09-04 05:17:00

你是怎么做到的？这些值未排序，但属于示例数组。答：[1..n][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²+y²=T'-T。

通过编写 x²+y²=（x+y）²-2xy => xy=（（S'-S）²-（T'-T））/2 来解决。

现在这些数字只是z中二次型的根：z²-（S'-S）z+（（S'-S）²-（T'-T））/2=0。

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

答案 1

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

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

编辑

假设数组的最大元素是假设和这里并且不存在于 a[] 中，因此 max 元素是。a[]Ba[]={1,2,4}35B=5

xor数组的所有元素aX
xor从 1 到到的所有元素Bx
查找最左边最位集xx = x &(~(x-1));
现在，如果比其他人用a[i] ^ x == xxora[i]pxorq
现在对于所有从 1 到如果比与其他与kBk ^ x == xxorpxorq
现在打印和pq

证明：

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

一旦我们元素和从1到5的数字，我们就留下了3和5，即。XORaXORx

现在，当我们发现它的最左边的位集只不过是3和5之间最左边最不同的位。（以及其中x3--> 0115 --> 101x = 010x = 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)

如果我们是它们之间的元素，我们会发现，同样，如果我们所有的元素都在它们之间，那么我们将得到5。答案由此而来。XORp3xorq

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

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

根的总和， = x + ySUM
根的乘积， = x * yPRODUCT

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

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

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

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