c++ - リスト内の中央値の位置

Question

ソートされていない配列があり、中央値の位置が必要です。O（n）で特定の配列の中央値を計算するアルゴリズムがいくつかあることは知っていますが、それらにはすべて、中央値の中央値やランダム選択など、配列の何らかの並べ替えが含まれています。

私は彼の中央値自体には興味がありません。配列内のその位置だけに興味があります。

O(n)でこれを行う方法はありますか? すべてのスワップを追跡すると膨大なオーバーヘッドが発生するため、別の解決策を探しています。

Answer 1

無限の数値ストリームの中央値を追跡するための O(n log n) アルゴリズムがあります。(リストを変更したくないので、ストリームとして扱うこともできます。) アルゴリズムには 2 つのヒープが含まれます。1 つは常に下半分の最大数を指し、もう 1 つは上半分の最小数を指します。アルゴリズムについては、http ://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/ で説明されています。最小限のカスタマイズで同じコードを使用できます。