从两个列表中查找缺少的数字

Question

问题: 假设我们有两个包含相同数字的未知整数列表.但是,其中一个列表缺少一个数字.找到丢失的号码最有效的是什么？

我的方法:嵌套了这样的循环:

public int findMissing(int [] list1,int [] list2){
   for(int i =0; i < list1.length(); i++){
      for(int j=0; j < list2.length(); j++){ 
          if(list1[i] != list2[j] && j == list2.length()-1) 
          return list2[j]; 
   }
}
return;

解释 将第二个列表中的每个项目与第一个列表中的每个项目进行比较.如果您在循环结束时到达并且第一个列表中缺少第二个列表中的数字,则返回该数字.

如果有更好的方法,请告诉我.在运行时间方面更好.

Answer 1

(list1中所有数字的总和) - (list2中所有数字的总和)=您要查找的数字.

假设第一个列表是包含附加号码的列表,否则返回该号码的负值.

Answer 2

比对两个列表求和(可能导致溢出)的更好的解决方案是对列表进行异或并将结果进行异或.该解决方案以线性时间运行,不会溢出.
这是一些证明它的代码

public class Main {
    public static int missingno(int[]first,int[]second) {
        int xor_val = 0;
        for (int i : first)
            xor_val ^= i;
        for (int i : second)
            xor_val ^= i;
        return xor_val;
    }
    public static void main(String[] args) {
        int[]a= {1,2,3,4,5,6,7,8};
        int[]b = {5,4,6,8,3,2,1};
        System.out.println(missingno(b,a));
    }
}

记住xor是一个非常多才多艺的操作员.它是可交换的和关联的,可以用来交换没有temp的变量.

我还想指出的是,另一个解决办法是保持一个HashMap(初始化为一个数字,不能在列表中)经过1短名单,标志着每个值存在,然后经过完整列表.如果你遇到一个尚未设定的值,你就找到了你遗失的元素.这样做的好处是它可以立即告诉您缺失元素的索引.