流中的字符

Question

这个问题是在一次采访中提出的。。

假设您的计算机正在从流中一个接一个地读取字符（在结束之前您不知道流的长度）。请注意，您只有一个字符的存储空间（因此您无法将读取的字符保存到类似strong的文件中）。当你读完后，你应该以同样的概率从流中返回一个字符。

如何处理这个问题？？知道吗？？

有办法解决这个问题吗？？

Answer 1

这是你要么知道要么不知道的技巧之一：

取第一个字符，概率为1/2取下一个，否则保留第一个，概率为1/3取下一个子，否则保留，以此类推

它之所以有效，是因为每次您选择概率为1/n的第n个字符，或保留概率为（1-n）/n/（n-1）），并且1-ns取消。