我在编码竞赛中遇到了这个问题[ related to data structure ] .
有一个树木的星球（真正的树木不是树木数据结构!!） . 它拥有数十亿甚至数万亿的树木 . 国王命令用碳约会找到所有树木的年龄中位数（年和整数） . （ Method does not matter. ）注意：中位数是排序的数字列表中的"middle number" .
Constraints:1. 已知最古老的树已有2000年历史 .2. 他们有一台机器可以存储从-infinity到infinity范围内的整数 .3. 但是一次可以存储在内存中的这种整数的数量是100万 .
所以，一旦你存储了100万个整数存储下一个整数，你必须删除已存储的整数 .
所以他们不得不在计算树木的年龄时跟踪中位数 .
他们怎么能这样做？
My approach
使用外部排序的变体对块中的年龄进行排序并将其写入文件中 .
应用k-way合并[用于块] .
上述方法的问题是它需要对文件进行两次扫描 .
我能想到 another approach 使用的信息 The oldest tree is known to be 2000 years old.
我们不能拿 count array [ as range of ages of tree is fixed ]？
我想知道 is there any better approach?
是否存在我们不需要将数据存储在文件中的方法？[ where only main memory is sufficient? ]
2 回答
您可以通过仅存储2001整数来完成此操作 . 创建一个包含不同年龄的数组
当你数一棵树
然后计算中位数是微不足道的 . 你似乎在你提到的第二种方法中遇到了这个解决方案，但是你说我想知道有没有更好的方法？
我不知道为什么你问是否存在主存足够的方法 . 2001年整数数组是否适合主内存？
使用上面的方法，您可以填充计数数组，然后通过迭代计数来计算中位数，并保持总和 . 当你的总和达到树木总数的一半时，你就得到了中位数 . 这需要一次遍历所有树来计算，再加上一些数字<= 2001的计数数组的一部分 . 所以这是O（n） . 相反，你可以随时跟踪这个阵列的中位数，但它不会真正改善解决方案 .
你推荐的方法（2001年的数组）是O（n），每棵树有一个快速操作，所以这是最佳的 .
好吧，几乎是最佳的 . 在计数期间的某个时刻，剩余树木的数量将不足以改变结果 . 例如，如果我计算了一半的树木，而且所有树木都是100年，那么我的答案是：100年 .
但如果树木在年龄上分散，则所需树木的数量将接近总数 .