关于数据结构的难题

Question

我在编码比赛中遇到了这个puzzle问题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]++

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

是否存在我们不需要将数据存储在文件中的方法？[只有主存储器就足够了？]

我不知道为什么你问是否存在主内存足够的方法.2001年整数数组是否适合主内存？

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