algorithm - 查找大量数字的中位数太大而无法放入内存

Question

我最近在一次采访中被问到这个问题。

有 N 个数字，太多以至于无法存储。它们分布在 k 个数据库表(未排序)中，每个表都可以放入内存。找出所有数字的中位数。

不太确定这个问题的答案。

Answer 1

有一些可能的解决方案:

• 外部合并排序 - O(n log n)
  您基本上是在第一遍对数字进行排序，然后在第二遍找到中位数。
• 订单统计分布式选择算法 - O(n)
  将问题简化为在未排序数组中查找第 k 个数字的原始问题。
• 计数排序直方图O(n)
  您必须假设有关数字范围的一些属性 - 范围是否适合内存？
• 如果知道其他数字的分布可以生成算法。

有关更多详细信息和实现，请参阅:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html