HashMap with Integers long time

Question

私は0から配列の長さまでの配列を持っていますが、いくつかの数がなくなっています。

public static Integer findNumber(Integer[] array){ 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(Integer number : array){ 
     map.put(number, 1); 
    } 
    for(Integer i=0; i<array.length; i++){ 
     if(map.get(i)==null) 
      return i; 
    } 
    return -1; 
} 

私はこれは良い解決策になるつもりだったと思ったが、置くことははるかに高速でカウント重複してソリューションを並べ替え、本当に長い時間がかかり、私がなぜ分かりません。 Hash for IntegerはInteger自体であるため、ハッシュを数えると時間が失われず、等号で反復されることもありません（数字に依存して、私は1つの複製だけを使って例を選びました）。ここで明白な何かが欠けているような気がする。私は初期容量と負荷率を指定しようとしましたが、状況を悪化させるだけです。何とかこれを最適化できますか？

パッティングには時間がかかりますが、解決策を見つけるまで繰り返すのではなく、パッティングは実行時間の95％と同じです。

Answer 1

もっと単純な解決策があると思います。試してみてください：

public static Integer findNumber(Integer[] array){ 

    for(Integer i=0; i<array.length; i++){ 
     if(i != array[i]) 
      return i; 
    } 
    return -1; 
} 

希望はあなたを助けます。

Answer 2

マップの代わりに、（プリミティブ）ブール値の配列を使用できます。アレイ上でその後 boolArray[number] = true;

、ループを、あなたがマップを使う、という場合は欠番

Answer 3

を見つける：最初のループでは、代わりに1を入れてのあなたは真の配列のセルを反転第二のループべきないアレイの上に行くのではなく、マップの値より、ヌル1を探して：あなたは簡単で高速道を行くことができ

map.values().stream().filter(v -> v == null).findFirst(); 

Answer 4

：和整数を配列にして、からそれを引く（それは数の合計です1からnまで）。残りの値は欠けている番号です。