Создать массив из 8-байтовых длин, который имеет 2 ^ 16 записей. Возьмите свои входные числа, сдвиньте младшие шестнадцать бит и создайте гистограмму.
Теперь вы будете считать в этой гистограмме, пока не дойдете до корзины, которая покрывает среднюю точку значений.
Пройдите снова, игнорируя все числа, у которых нет такого же набора старших бит, и составьте гистограмму младших бит.
Считайте по этой гистограмме до тех пор, пока не достигнете корзины, которая покрывает среднюю точку (всего списка) значений.
Теперь вы знаете медиану в O(n) времени и O(1) пространстве (на практике, до 1 МБ).
Вот пример кода Scala, который делает это:
def medianFinder(numbers: Iterable[Int]) = {
def midArgMid(a: Array[Long], mid: Long) = {
val cuml = a.scanLeft(0L)(_ + _).drop(1)
cuml.zipWithIndex.dropWhile(_._1 < mid).head
}
val topHistogram = new Array[Long](65536)
var count = 0L
numbers.foreach(number => {
count += 1
topHistogram(number>>>16) += 1
})
val (topCount,topIndex) = midArgMid(topHistogram, (count+1)/2)
val botHistogram = new Array[Long](65536)
numbers.foreach(number => {
if ((number>>>16) == topIndex) botHistogram(number & 0xFFFF) += 1
})
val (botCount,botIndex) =
midArgMid(botHistogram, (count+1)/2 - (topCount-topHistogram(topIndex)))
(topIndex<<16) + botIndex
}
и здесь он работает над небольшим набором входных данных:
scala> medianFinder(List(1,123,12345,1234567,123456789))
res18: Int = 12345
Если у вас хранятся 64-битные целые числа, вы можете использовать одну и ту же стратегию за 4 прохода.