创建一个具有2 ^ 16项的8字节长数组。输入您的输入数字，移出最低的16位，然后创建直方图。

现在，您可以在该直方图中进行计数，直到到达覆盖值中点的区域。

再次通过，忽略所有没有相同的最高位集合的数字，并对最低位进行直方图绘制。

计数直方图，直到到达覆盖值（整个列表）中点的区域。

现在您知道了O(n)时间和O(1)空间的中位数（实际上，不到1 MB）。

这是一些执行此操作的示例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个遍中使用相同的策略。