[解決済み] リストにない最小の整数を求める

質問

私の同僚が使っている面白いインタビューの質問です。

非常に長い、ソートされていない符号なし64ビット整数のリストが与えられたとします。を満たす最小の非負の整数をどのように見つけますか? は が発生する最小の非負整数をどのように見つけるか？

フォローアップ：ソートによる明白な解決策が提案されたので、O(n log n)よりも速くそれを行うことは可能でしょうか？

フォローアップ：あなたのアルゴリズムは、例えば1GBのメモリを持つコンピュータ上で実行されなければなりません。

明確化：リストはRAM上にありますが、それを大量に消費する可能性があります。あなたは事前にリストのサイズ、例えばNを与えられています。

どのように解決するのですか？

もしデータ構造がその場で変更可能で、ランダムアクセスをサポートしているならば、O(N)個の時間とO(1)個の追加スペースで実行可能です。配列を順次調べ、すべてのインデックスについて、インデックスにある値を値で指定されたインデックスに書き込み、その場所にあるすべての値を再帰的にその場所に置き、値 > N を捨てます。この結果、最大で 3N の比較となり、一時的なスペースは数個の値しか使用しなくなります。

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N