数据结构上的一个难题
我在编码竞赛中遇到了这个related to data structure puzzle 。
有一个树行星（真正的树木不是树数据结构!!）。 它拥有数十亿甚至数万亿棵树。 国王命令使用说碳定年来找出所有树木的年龄中位数（年数和整数）。 （ Method does not matter. ）注意：Median是排序数字列表中的“中间数字”。
约束：
1.最古老的树被称为是2000年的历史。
2.它们具有能够在范围存储整数从负无穷大到正无穷大单一机器。
3.但是，可以一次被存储在存储器中，例如整数的数是1百万。
所以，一旦你存储了100万个整数来存储下一个整数，你必须删除已存储的整数。
所以他们不得不跟踪中位数，因为他们继续计算树木的年龄。
他们如何做到这一点？
我的方法
使用外部排序的变体来对块中的年龄进行排序并将其写入文件中。
应用k-way合并[对于块]。
上述方法的问题是它需要对文件进行两次扫描。
我可以想到另一种使用信息The oldest tree is known to be 2000 years old. 方法 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? ]
你可以通过存储2001年的整数来做到这一点。 创建一个不同可能年龄的数组
ages[2001] // [0..2000]
当你数一棵树时
ages[thisAge]++
然后计算中位数是微不足道的。 您似乎在提到的第二种方法中遇到了这种解决方案，但后来你说我想知道是否有更好的方法？
是否存在任何我们不需要将数据存储在文件中的方法？[只有主存储器是足够的？]
我不承认为什么你问是否存在任何主存空间足够的方法。 2001年的整数数组是否适合主内存？
使用上面的方法，您可以填充您的计数数组，然后通过遍历计数来计算中位数，并保留总数。 当你的总数达到树木总数的一半时，你的中位数。 这需要一遍遍所有的树来计数，再加上一些数字<= 2001的部分数组。 所以这是O（n）。 相反，你可以随时跟踪这个数组的中位数，但它不会真正改善解决方案。
你推荐的方法（2001年的数组）是O（n），每个树有一个快速操作，所以这是最优的。
那么，几乎是最佳。 在计数期间的某一点，剩余树木的数量将不足以改变结果。 例如，如果我计算一半树木的数量+1，并且都是100年，那么我的答案是：100年。
但是，如果树木年龄分散，那么所需树木的数量将接近总数。
链接地址: http://www.djcxy.com/p/70789.html