查找两个列表中的缺失编号

问题：可以说我们有两个包含相同编号的未知整数列表。但是，其中一个列表缺少一个数字。找到缺失号码最有效的是什么？查找两个列表中的缺失编号

我的方法：嵌套的for循环是这样的：

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;

说明比较第二列表中的每个项目在第一列表中的每个项目。如果您在循环结束时到达并且第一个列表中缺少第二个列表中的数字，则返回该数字。

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

来源

2013-06-04 Stranger

列表的顺序是否相同？ – ajon

对于小列表，你可以逃避这一点。但是，随着名单的增长，这个规模会很小。 –

一个问题：数组中的所有元素都是唯一的吗？ – fge

（来自list1的所有数字的总和） - （来自list2的所有数字的总和）=您要查找的数字。

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

来源

2013-06-04 18:00:39

不适用于[1 1]，[1 2]等列表，在这种情况下，2只在一个列表中，而不在另一个列表中 – bengoesboom

+1 :)我没有考虑这个解决方案 – Maroun

@bengoesboom - 是的，但我理解问题的方式是一个列表有一个额外的数字。 –

如果列表应该是相同的，您可以对它们进行排序。那么你将不需要嵌套循环。您可以在同一位置查看两个列表，并且它们应该相同。如果不是，其中一个列表是不同的（取决于你认为哪个列表是正确的）。运行时在这一点上是线性的，以检查整个列表。

来源

2013-06-04 18:05:10 Vahlkron

不要忘记实际排序的性能！ – bengoesboom

好点。这将是线性+排序时间。谢谢！ :) – Vahlkron

比汇总两个列表（可能导致溢出）更好的解决方法是异或列表并将结果异或。该解决方案在线性时间内运行，无法溢出。
下面是一些代码来证明这一点

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-短列表，将每个值标记为存在，然后通过完整的列表。如果你遇到一个尚未设定的值，你会发现你缺少的元素。这样做的好处是可以立即告诉你缺少元素的索引。

来源

2013-06-19 04:29:29 aaronman

+1它可以说没有比这更快的速度，并且不会遭受可能的错误情况。 –

@LievenKeersmaekers可惜它不会得到其他答案的关注，我其实在接受采访时竟然有这个 – aaronman

的确如此。你迟到了，但狂热的读者可能仍然会选择*（投票）*。 –

查找两个列表中的缺失编号

回答

相关问题