3

質問: 同じ数値を含む 2 つの未知の整数リストがあるとします。ただし、リストの 1 つに番号がありません。不足している数を見つけるのに最も効果的なのは何ですか?

私のアプローチ: 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;

説明 は、2 番目のリストの各項目を最初のリストのすべての項目と比較します。ループの最後に到達し、2 番目のリストの番号が最初のリストにない場合は、その番号を返します。

これを行うより良い方法があれば教えてください。実行時間の点で優れています。

4

3 に答える 3

10

(list1 のすべての数値の合計) - (list2 のすべての数値の合計) = 探している数値。

これは、最初のリストが追加の数値を含むものであると想定しています。それ以外の場合は、その数値の負の値を返します。

于 2013-06-04T18:00:39.510 に答える
10

2 つのリストを合計する (オーバーフローが発生する可能性がある) よりも優れた解決策は、リストを XOR し、結果を一緒に XOR することです。このソリューションは線形時間で実行され、オーバーフローすることはありません。
ここにそれを証明するためのいくつかのコードがあります

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 なしで変数を交換するために使用できます。

また、別の解決策として、ハッシュマップ (リストに入れることのできない数値に初期化) を維持し、1 つの短いリストを調べ、各値を存在としてマークしてから、完全なリストを調べることも指摘したいと思います。設定されていない値に遭遇した場合は、欠落している要素が見つかりました。これの利点は、欠落している要素のインデックスがすぐにわかることです。

于 2013-06-19T04:29:29.503 に答える