#8 Heaps: Find the Running Median
以下のような入力が与えられる。 1行目は、データの数、2行目以下はデータリストに追加する数となっている。
6 12 4 5 3 8 7
上記の入力が与えられた場合、1行毎にデータリストへ値を追加し、その時点でのデータリストの中央値を計算し以下のフォーマットで出力する。
12.0 8.0 5.0 4.5 5.0 6.0
solution
rubyで解いた。 rubyのsortメソッドを使えばarrayのソートについては何も考える必要はないが、本問題はそれではパスできないテストケースが用意されている(timeoutを起こす)。そのため、処理速度を考慮したコードを書く必要がある。 この問題では、1行毎にデータがリストへ追加されるため、ソートアルゴリズムとして挿入ソートを採用した。
def insertSort(ary, num) if ary.empty? ary << num else left, right, mid = 0, ary.length - 1, 0 while left < right do mid = right <= 0 ? 0 : (left + right) / 2 if num < ary[mid] right = mid - 1 else left = mid + 1 end end if num < ary[left] ary.insert(left, num) else ary.insert(left + 1, num) end end return ary end input = $stdin.read.split("\n").map(&:to_i) n, nums, ary = input.shift, input, [] nums.each do |num| ary = insertSort(ary, num) len = ary.length puts (ary[(len - 1) / 2] + ary[len / 2]) / 2.0 end
中央値とは
中央値(ちゅうおうち、英: median)とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。中央値の事を、メディアン、メジアン、中間値とも呼ぶ。ただし、「中間値の定理」の中間値はこの意味ではない。
挿入ソートとは
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
感想
中央値算出は単純に見えて、案外嵌りやすい気がする。良問。