假设您有固定数量的 k 存储位置，并且有两个计数器的空间。您将收到 ñ 随机顺序的项目（的所有排列 ň
项目也同样可能）。收到每个项目后，您可以将其存储在 k个
位置之一（丢弃先前存储的值之一），也可以丢弃该项目。您也可以递增或递减两个计数器。任何丢弃的物品都无法找回。

问题是

1. 有什么策略可以最大程度地提高您找到确切中位数的可能性？
2. 那是几率？

显然，如果 k > n /
2，我们可以找到中位数。通常，似乎试图将丢弃的高值的数量保持等于丢弃的低值的数量的相同策略应该是最佳的，但是我不确定如何证明它，也不确定如何找出它发现的可能性中位数。

同样感兴趣的是我们不知道的情况下 ñ 但要知道的概率分布 ñ 。

编辑： 现在假设值是不同的（没有重复。）但是，如果您也可以解决非不同的情况，那将是令人印象深刻的。