如何找到丢失的数字，给定：两个数组作为输入，并找到第一个数组中存在但第二个数组中缺少的数字

Question

如何找到丢失的号码？

给定：两个数组作为输入，并找到第一个数组中存在但第二个数组中缺失的数字。

public class Array2 
 {
public void missingnos(int a[],int b[])
{
    for(int i=0;i<a.length;i++)
    {
        for(int j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                int c=a[i];
                a[i]=a[j];
                a[j]=c;
            }
        }
        System.out.print(a[i]);
    }
    for(int i=0;i<b.length;i++)
    {
        for(int j=i+1;j<b.length;j++)
        {
            if(b[i]>b[j])
            {
                int c=b[i];
                b[i]=b[j];
                b[j]=c;
            }
        }
        System.out.print(b[i]);
    }
    int d[]=new int[a.length];
    d=b;
    int missing=0;
    for(int i=0;i<b.length;i++)
    {
        if(a[i]!=d[i])
        {
            missing=a[i];
            break;
        }
    }
    System.out.println();
    System.out.print(missing);
}
public static void main(String[] args) {
    Array2 a2= new  Array2();
    int a[]={1,4,3,5,6};
    int b[]={4,1,5,3};
    a2.missingnos(a,b);

}

}

测试用例：当我分别从数组“a”和“b”中删除 6 和 3 时，我得到的答案为 3，这是正确的，但是当我不删除时，我得到的答案为 0。

为什么会这样？

Answer 1

这里有一种在 O(1) 辅助空间和 O(n) 时间内解决这个问题的方法。该解决方案受以下约束：
1) arr2 仅缺少 arr1 中的一个元素。
2) arr2.length=arr1.length-1 OR arr2 将缺失的元素替换为 0。

解决方案：只需对两个数组的所有元素进行异或。结果整数就是答案

代码：

public static void findMissing(){
    // TODO Auto-generated method stub
    int[] arr1={3,7,2,90,34};
    int[] arr2={2,7,34,3};  
    int xor=0;
    for(int i=0;i<arr1.length;i++){
        xor^=arr1[i];
    }
    for(int i=0;i<arr2.length;i++){
        xor^=arr2[i];
    }
    System.out.println("missing number: "+xor);
}

为什么有效？说 arr1={1,2,3,4} 和 arr2={1,2,4}。取所有元素的异或 =>
1^2^3^4^1^2^4
= (1^1)^(2^2)^(4^4)^3
= 0^0^0^3
=3

RP-提出的另一种解决方案也很好，在相同的空间和时间复杂度下解决了这个问题，但是在计算和时有可能溢出。