配列中のK番目に小さい要素

Question

nのサイズの配列が与えられた場合、O（1）スペース（メジアンの中央値ではない）を使用する決定論的アルゴリズム（クイックソートではない）が与えられ、K ' 。

nlognで配列をソートする、またはnkで最小k時間を見つけるなどの明白な解決策がありますが、それを実行するより良い方法があると確信しています。それはライナーである必要はありません（私はそれができればそれを疑う）。

ヘルパーに感謝します。

Answer 1

（余分なスペースが浪費されないように）min-heap（can be built in O(n) time）にアレイを配置した後、O(log n)時間を要する各whicihのkエキス分操作は、行います。だから、あなたはO(n + k*log n)の時間を持っています。 （k <= n以来最悪の場合はO(n log n)です。）

スペースの複雑さは、O(1)あるか、あなたは我々が変更した配列を数える場合、O(n)。 アルゴリズムは配列を必要とするため、配列によって寄与する空間がO(n)である必要があります。ヒープによって発生する追加スペースコストはO(1)です。

このアプローチが正しいことは明らかです。最初のextract-minは最小の要素を返します（ヒープから削除します）。 2番目のextract-minは2番目に小さい要素を返します（ヒープから削除します）。 ...; k番目のextract-minは、k番目の最小要素を返します（ヒープから削除します）。

より "はるかに大きい"場合は、max-heapを使用して同様の方法を使用して(n-k)番目の最大要素を検索することでスピードアップできます。