3

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

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

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;

解释 将第二个列表中的每个项目与第一个列表中的每个项目进行比较。如果您到达循环末尾并且第二个列表中的数字在第一个列表中丢失，则返回该数字。

让我知道是否有更好的方法来做到这一点。在运行时间方面更好。

4

3 回答 3

10

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

假设第一个列表是包含附加数字的列表，否则返回该数字的负值。

于 2013-06-04T18:00:39.510 回答
10

比将两个列表相加（可能导致溢出）更好的解决方案是将列表异或并将结果异或在一起。该解决方案在线性时间内运行并且不会溢出。
这是一些证明它的代码

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 是一个非常通用的运算符。它是可交换的和关联的，可用于在没有临时变量的情况下交换变量。

我还想指出，另一种解决方案是维护一个 hashmap（初始化为一个不能在列表中的数字）遍历 1-short 列表，将每个值标记为存在，然后遍历完整列表。如果您遇到尚未设置的值，则您已找到缺少的元素。这样做的好处是它会立即告诉您丢失元素的索引。

于 2013-06-19T04:29:29.503 回答
3

If the lists are supposed to be the same, you can just sort them. Then you won't need to nest loops. You can check both lists at the same location, and they should be equal. If not, one of the lists is different (depends on which list you are deeming to be correct.) The runtime would be linear at that point to check the entire list.

于 2013-06-04T18:05:10.303 回答