median - 連続中央値を見つける

Question

新しい入力が追加されるたびに更新される特定の入力の中央値をどのように計算しますか? 例えば：

• 1 - 中央値は 1
• 1,2 - 中央値は 3/2
• 1,2,3 - 中央値は 2

Answer 1

O（n）時間未満でそれを行う方法がわかりません。

現在のアイテムのソートされたリストを保持する必要があります。新しいアイテムが届くたびに、正しい位置に挿入する必要があります。これには O(n) 時間が必要です。

新しい中央値の計算は初歩的です。新しい N が奇数の場合は配列 [(N-1)/2]、それ以外の場合は (配列[(N)/2] + 配列[(N)/2 - 1] ) / 2 です。