查找兩個列表中的缺失編號

問題：可以說我們有兩個包含相同編號的未知整數列表。但是，其中一個列表缺少一個數字。找到缺失號碼最有效的是什麼？查找兩個列表中的缺失編號

我的方法：嵌套的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

的確如此。你遲到了，但狂熱的讀者可能仍然會選擇*（投票）*。 –

查找兩個列表中的缺失編號

回答

相關問題