8

我在编码比赛中 遇到了这个puzzle问题[ ]。related to data structure

有一颗树的星球（真正的树不是树的数据结构！！）。它有数十亿甚至数万亿棵树。国王命令使用碳测年法找出所有树木的年龄中位数（以年和整数为单位）。( Method does not matter.) 注意：中位数是排序后的数字列表中的“中间数字”。

限制条件：
1.已知最古老的树有 2000 年的历史。
2.他们有一台机器，可以存储从 -infinity 到 +infinity 范围内的整数。
3.但是一次可以存储在内存中的这种整数的数量是 100 万个。

所以，一旦你存储了 100 万个整数来存储下一个整数，你必须删除已经存储的一个。
因此，当他们继续计算树木的年龄时，他们必须以某种方式跟踪中位数。
他们怎么能做到这一点？

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

我可以想到另一种使用信息的方法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?]

4

2 回答 2

9

您可以通过仅存储 2001 个整数来做到这一点。创建一个包含不同可能年龄的数组

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

当你数一棵树时

ages[thisAge]++

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

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

我不明白你为什么问是否存在任何主内存足够的方法。2001 整数数组不适合主内存吗？

使用上述方法，您可以填充计数数组，然后通过迭代计数来计算中位数，同时保持总和。当您的总和达到树木总数的一半时，您就有了中位数。这需要遍历所有的树进行计数，再加上遍历某个数字 <=2001 的计数数组的一部分。所以这是 O(n)。相反，您可以随时使用此数组跟踪中位数，但这并不会真正改善解决方案。

于 2012-06-24T13:23:54.360 回答
2

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

嗯，几乎是最优的。在计数过程中的某个时刻，剩余树的数量将不足以改变结果。例如，如果我数一半 + 1 棵树，并且所有树都正好有 100 年的历史，那么我就有答案：100 年。

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

于 2012-06-24T13:37:00.740 回答