#8/20 Heaps: Find the Running Median [Cracking the Coding Interview Challenges]

#8 Heaps: Find the Running Median

www.hackerrank.com

以下のような入力が与えられる。 1行目は、データの数、2行目以下はデータリストに追加する数となっている。

上記の入力が与えられた場合、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

github.com

中央値とは

中央値（ちゅうおうち、英: median）とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。中央値の事を、メディアン、メジアン、中間値とも呼ぶ。ただし、「中間値の定理」の中間値はこの意味ではない。

中央値 - Wikipedia

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソート - Wikipedia

感想

中央値算出は単純に見えて、案外嵌りやすい気がする。良問。