algorithm - 配列内で欠落している最小の数を見つけます

Question

重複の可能性：
リストにない最小の整数を見つける

インタビューでこの質問をされました

ソートされていない配列が与えられた場合、欠落している最小の数を見つけます。すべての数値が正であると想定します。

入力={4,2,1,3,678,3432}

出力=5

それを分類することが私の最初のアプローチでした。私の2番目のアプローチは、ブールフラグ配列を使用することです。2番目のアプローチは、多くのスペースを占有します。

これ以外に良いアプローチはありますか？

Answer 1

与えられた配列の長さが であるとしNます。Nboolean-flag アプローチを使用できますが、明らかに大きすぎて答えに影響を与えないため、考慮に入れるよりも大きい数値を使用する必要はありません。bitmapスペースを節約するために を検討することもできます。

Answer 2

アンクルンクルの代替ソリューションは次のとおりです。

k := 1
Make an array of 2^k booleans, all initially set to false
For every value, V, in the array:
  if V < 2^k then:
    set the V'th boolean to true
Scan through the booleans, if there are any falses then the lowest one indicates the lowest missing value.
If there were no falses then increment k and go to step 2.

これは O(n log s) 時間と O(s) 空間で実行されます。n は入力配列のサイズで、s は存在しない最小値です。連続する反復で最小値を再チェックしないことでより効率的にすることができますが、それは制約を変更しません。