我有一个过程会产生价值，并且我会观察到。当过程终止时，我想计算这些值的中位数。
如果必须计算平均值，则可以存储求和值和生成值的数量，因此需要O（1）内存。中位数怎么样？有没有办法保存来自存储所有值的明显O（n）？
编辑： 对2种情况感兴趣：1）已知流长度，2）未知。
您将需要至少存储ceil（n / 2）点，因为前n / 2点中的任何一个都可能是中位数。仅存储点并找到中位数可能是最简单的。如果保存ceil（n / 2）点很有价值，则将前n / 2个点读入排序列表中（最好是二叉树），然后在添加新点时将低点或高点丢弃，并保持跟踪任一端抛出的点数。
编辑：
如果流的长度是未知的，那么正如斯蒂芬在评论中所观察到的那样，显然，我们别无选择，只能记住一切。如果可能有重复的项目，我们可以使用Dolphins的存储值和计数的思想来节省一些内存。
