c++ - K次統計量検索

Question

そこで、ソートされていない配列で k 番目に大きい要素を見つけるために、独自の k 次統計検索を実装しました。ただし、使用したアルゴリズム (ここで見つけることができます: http://pine.cs.yale.edu/pinewiki/QuickSelect ) が要素自体を返すことに気付きましたが、実際には k 番目に大きいインデックスを返したいと思いますエレメント。代わりにそれを行う方法はありますか？

Answer 1

QuickSelectでは、k番目の統計の元のインデックスを返すことはできません。アルゴリズムはインプレースであり、アレイをスクランブルします。最初に元の配列のコピーを作成する必要があります（または、要素が移動するときに要素を追跡します。これもO（n）メモリを使用し、はるかに複雑です）。