面试问题:从大量的整数中找到中位数

Question

有一个包含10G(1000000000)个整数的文件,请找这些整数的中位数.你有2G内存来做这件事.有人能想出一个合理的方法吗？谢谢!

Answer 1

创建一个8字节长的数组,其中包含2 ^ 16个条目.获取输入数字,移出最后16位,然后创建直方图.

现在你在直方图中计算,直到你到达覆盖值中点的bin.

再次通过,忽略所有没有相同顶部位的数字,并制作底部位的直方图.

通过该直方图向上计数,直到到达覆盖(整个列表)值的中点的bin.

现在您知道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次传递中使用相同的策略.

Answer 2

您可以使用Medians of Medians算法.