面试题[数学与概率]: 从数据流中随机选一个数

题目：输入一段int型数据流，输入未完成之前并不知道数据流的长度，，要求在O(1)空间复杂度的前提下随机选出一个元素，并保证每一个元素被选中的概率是一样的。

我的解法如下：

假如输入的数据流依次是10、20、30、40、……

收到10时：以概率1选择10； 收到20时：以概率1/2选择10，以概率1/2选择20； 收到30时：以概率2/3选择上一次选到的元素，以概率1/3选择30； 收到40时：以概率3/4选择上一次选到的元素，以概率1/4选择40； …… 收到第N个数时：以概率(n-1)/n选择上一次选到的元素，以概率1/n选择当前元素。

敢于奋斗的人，心中不怕困难。