問題: 入力は (必ずしもソートされていない) シーケンス S = k1, k2, ..., kn の任意の数 n です。1 <=i, j<=n に対して、形式 min{ki,kj} の n² 数のコレクション C を考えてみましょう。Cの中央値を求めるO(n)時O(n)空間アルゴリズムを示します。
これまでのところ、さまざまなセット S について C を調べることで、C 内の S の最小数のインスタンスの数が (2n-1) に等しく、次に小さい数 (2n-3) などであることがわかりました。最大数のインスタンスが 1 つだけあります。
この情報を使用して C の中央値を見つける方法はありますか?
いくつかの可能性があります。私が気に入っているのは Hoare のSelectアルゴリズムです。基本的な考え方はクイックソートに似ていますが、再帰する場合、探している番号を保持するパーティションにのみ再帰する点が異なります。
たとえば、100 個の数値の中央値が必要な場合は、Quicksort と同様に配列を分割することから始めます。2 つのパーティションが得られます。そのうちの 1 つは 50番目の要素を含みます。そのパーティションで選択を再帰的に実行します。パーティションに要素が 1 つだけ含まれるようになるまで続行します。これが中央値になります (選択した別の要素についても同じことができることに注意してください)。
はい、良いパズルです。あなたが言った線で中央値が発達しているのを見つけることができます。
C では、max(k) が 1 回出現し、次に高い値が 3 回、次に高い値が 5 回、というように発生します。
C の要素を並べると、m 番目に大きい数の左側の要素の数は m^2 (奇数の合計) になります。
関心のある数値 (中央値を計算するため) n が奇数の場合、(n^2+1)/2 = alpha b です。n が偶数の場合、alpha1 = n^2/2 および alpha2 = n^2/2+1 となりますが、alpha1=n^2/2 は決して平方数ではありません => alpha1 のすぐ右側の数は alpha1 と等しくなります (最初の m 個の奇数の合計は 2 乗) => alpha1=alpha2.
つまり、m^2 (最初の m 個の奇数の合計) が (n^2/2) よりわずかに大きくなるように m を決定することになります。
つまり、m=ceiling(n/sqrt(2)) と、元のシーケンスで m 番目に大きい数を決定することになります (m 番目に大きいものを見つけるか、(nm-1) 番目に小さいかを見つけるのが最適化です)。
m 番目に大きい数を簡単に見つけることができます (左から最初の m 個の最大数に注目し続けるだけです)。
ウィキペディアには、選択アルゴリズムに関する優れた記事があります。C++ を使用している場合、STL には平均して線形時間のnth_element()アルゴリズムが含まれています。