algorithm - 一个关于数据结构的谜题

Question

我在一次编码比赛中遇到了这个难题问题[与数据结构相关]。

有一个树星球(真正的树不是树数据结构!!)。它有数十亿甚至数万亿棵树。国王命令使用碳测年法找出所有树木的年龄中位数(以年和整数表示)。 (方法无关紧要。) 注意:中位数是经过排序的数字列表中的“中间数”。

约束:
1.已知最古老的树有 2000 年的历史。
2. 他们有一台机器可以存储从 -infinity 到 +infinity 范围内的整数。
3. 但是内存中一次可以存储的这样的整数的个数是100万个。

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

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

我可以想到另一种方法，它使用信息已知最古老的树有 2000 年历史。
我们不能取一个计数数组 [因为树的年龄范围是固定的]吗？

我想知道有没有更好的方法？
有没有什么方法不需要把数据存到文件里？[只用主存就够了？]

Answer 1

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

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

当你数一棵树时

ages[thisAge]++

然后计算中位数就很简单了。 你似乎在你提到的第二种方法中找到了这个解决方案，但是你说 我想知道有没有更好的方法？

Does there exist any method where we do not need to store the data in the file?[where only main memory is sufficient?]

我不明白你为什么要问是否存在主内存足够的方法。 2001 整数数组不能放入主内存吗？

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