关于数据结构的一个难题

Question

我在编码竞争中遇到了这个问题[related to data structure]。

有一颗行星树（真正的树不是树数据结构!!）。它拥有数十亿甚至数万亿棵树。国王命令使用说碳定年来找出所有树木的年龄中位数（年数和整数）。 （Method does not matter.） 注意：中位数是排序数字列表中的“中间数字”。

约束：
1.最古老的树被称为是2000年的历史。
2.他们有单机可以存储整数范围从-infinity到+ infinity。
3.但是，一次可以存储在内存中的这种整数的数量是100万。

因此，一旦您存储100万整数来存储下一个整数，您必须删除已存储的整数。
因此，他们不得不跟踪中位数，因为他们继续计算树木的年龄。
他们如何做到这一点？

我的做法
使用外部排序的变体，在&它们写入文件块的年龄排序。
应用k-way合并[对于块]。
上述方法的问题是它需要对文件进行两次扫描。

我能想到的另一种方法它采用The oldest tree is known to be 2000 years old.
我们不能采取count array [as range of ages of tree is fixed]的信息？

我想知道有没有更好的方法？
是否存在，我们不需要将数据存储在文件中的任何方法？[where only main memory is sufficient?]

Answer 1

您可以通过存储只是2001整数做到这一点。创建不同的可能年龄

ages[2001] // [0..2000] 

数组时，你算一棵树

ages[thisAge]++ 

然后计算中位数是微不足道的。 您似乎在提到的第二种方法中遇到了此解决方案，但后来您说 我想知道是否有更好的方法？

是否存在任何方法，我们不需要将数据存储在 文件？[只有主内存就足够了？]

我不undertstand你为什么问我有没有存在主存满足的任何方法。 2001年的整数数组是否适合主内存？

使用上述方法，您可以填充您的计数数组，然后通过迭代计数来计算中位数，并保留总计。当你的总数达到树木总数的一半时，你的中位数。这需要一遍遍所有的树来计数，再加上一些数字的部分通过< = 2001。所以这是O（n）。相反，你可以随时跟踪这个数组的中位数，但它不会真正改善解决方案。

Answer 2

你推荐的方法（2001年的数组）是O（n），每棵树有一个快速操作，所以这是最优的。

那么，几乎是最优的。在计数期间的某一点，剩余树木的数量将不足以改变结果。例如，如果我计算一半树木的数量+1，并且都是100年，那么我的答案是：100年。

但是，如果树木年龄分散，那么所需树木的数量将接近总数。