数据结构问题谜题

Question

我在一次编程比赛中遇到了这个与数据结构相关的谜题。

某个星球上有无数棵树（真正的树木，不是树形数据结构！）。国王下令使用碳定年法找到所有树木的年龄（以整数年为单位）的中位数。（方法不重要）

限制条件：
1. 最老的树被认为有2000岁。
2. 他们只有一台机器，可以存储范围从负无穷到正无穷的整数。
3. 但是每次可以同时存储在内存中的这种整数的数量最多为100万。

因此，一旦您存储了100万个整数，为了存储下一个整数，您必须删除已经存储的整数。
因此，他们必须想办法随着树龄的统计来跟踪中位数。
他们该如何实现呢？

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

我能想到另一种方法，它使用信息最老的树被认为有2000岁。
我们不能采用一个计数数组[因为树龄的范围是固定的]吗？

我想知道是否存在更好的方法？
是否存在一种不需要将数据存储在文件中的方法？[只需要主内存就足够了？]

- Green goblin

---

不确定这是否有帮助：哈夫曼编码 - lllluuukke

使用 Gödel 编码将所有树的年龄存储在一个内存位置中，这算作作弊吗？ - Ishtar

你的第二种方法，只需要2001个整数，对我来说看起来非常不错。 - hatchet - done with SOverflow

即使没有使用哥德尔编码，您仍然可以使用单个整数作为无限数据存储器。 - Kaito

我们曾经有一棵4500年的古老树，但我们砍掉了它。http://en.wikipedia.org/wiki/Prometheus_(tree)# - Colonel Panic

Answer 1

你可以通过存储仅有2001个整数来实现此目标。创建一个包含各种可能年龄的数组即可。

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

当你计算一棵树时

ages[thisAge]++

计算中位数很容易。你似乎在提到的第二种方法中想到了这个解决方案，但是接着你问是否有更好的方法？

存在不需要将数据存储在文件中即可仅使用主内存的方法吗？

我不明白您为什么要问是否存在仅使用主内存的方法。2001个整数的数组难道不适合主内存吗？

使用上述方法，可以填充计数数组，然后通过迭代计数来计算中位数，同时保持总和。当总和达到树的总数的一半时，即可得出中位数。这需要对所有树进行一次遍历以进行计数，并通过一些数量小于等于2001的计数数组进行遍历。因此，这是O(n)复杂度。您可以在进行操作时跟踪中位数，但这实际上并没有改善解决方案。

- hatchet - done with SOverflow

Answer 2

你建议的方法（一个2001年的数组）是O(n)的，每棵树只需要一个快速操作，因此这是最优的。

嗯，几乎是最优的。在计数期间，剩余的树木数量有时会不足以改变结果。例如，如果我数一半加一棵树，而所有树木都恰好100岁，则我得到的答案是100岁。

但如果树木年龄分散，则所需树木的数量将接近总数。

- djconnel