unique な配列の中央値を O(N) で計算する

linear-median.rb

# 中央値以下の最大の要素を取得する
def linear_median(array)
  n = array.size
  return array.sort[(n - 1) / 2] if n <= 3
  case n % 3
  when 0
    pivot = linear_median((0 ... n / 3).map { |i| array[i * 3, 3].sort[1] })
    remain = []
    (n / 3).times do |i|
      l, c, r = array[i * 3, 3].sort
      case c <=> pivot
      when 0
        remain << l << c << r
      when -1
        remain << c << r
      when 1
        remain << l << c
      end
    end
    linear_median(remain)
  when 1
    linear_median(array - [array.min])
  when 2
    linear_median(array - array.minmax)
  end
end