文本流如何等概率获取指定字符

存在一个等概率的0、1发生器。
给一个文本流，给定一个指定的字符'x'，写一个函数，等概率地返回'x'的一个文本流偏移（就是'x'在字符串中的位置，比如文本为 axbx，那么x的偏移为{1, 3}，最后你需要获得1或者3，概率分别为1/2
假设文本流每个字符1字节）

============================基本问题=========================================
-----------------------------------------------------------------------------
已知等概率的0-1生产器uint make0~1()，求等概率的0~n生产器uint make0~n(uint n)
uint make0~n(uint n)
{
   //...
   //make0~1();
   //...
   return ?; //
}
具体什么方法使得make0~n最高效还是大家去想吧。。。
这里高效的意思是很快就能够返回结果。

-----------------------------------------------------------------------------
=============================================================================

【方法一】
设共有N个字符.
for(;;)
{
    产生0~N-1的随机数r
    if(A[r]=='x') return r;
}

分析：因为0~N-1是等概率的，产生'x'的位置也是等概率的.
缺陷：循环return的概率是R/N (R为'x'的个数)
若N超级大R很小,for循环很难return.

【方法二】
1：vector a_pos;//从头到尾记录'x'出现的位置
2：这里有R==a_pos.size(). 产生0~R-1的随机数r
3：取a_pos[r]即可。

缺陷：当R很大时空间开销很大。
比方法一的优势在于： 这个无须循环一下就可return.

【方法三】
先遍历一遍字符串，记下有'x'出现的次数为R；
产生0~R-1 的随机数 r
再遍历一遍字符串获取第r个'x'的位置

缺陷：最坏情况要遍历两遍字符串
优势：克服了方法一和二的缺陷

=========面试官会问，还有没有更好的方法=========================
【方法四】
有没有只遍历一遍就OK的方法呢？
直观的，我们每碰到一个'x'，设当前碰到的'x'的位置是i，我们可以以某个概率p去获取这个
'x'。此时获取'x'的概率绝对不是1/R，因为我们还不知道R的确切数字呢。
我们仍然需要继续遍历i之后的字符串，然后覆盖之。。。

于是列个方程组（*），获取第一个的概率是P(1)，获取第i个的概率是P(i)，获取第R个的概率是P(R)
满足：
P(1)(1-P(2))(1-P(3))...(1-P(R))=1/R
P(2)(1-P(3))...(1-P(R))=1/R
P(3)(1-P(4))...(1-P(R))=1/R
...
P(R-1)(1-P(R))=1/R
P(R)=1/R

上述方程组的思想是：每个字符获取的概率为1/R,遍历到它时能获取它，其后的所有该字符都不会获取。

求P(i)，得：
P(R)=1/R
P(R-1)=1/(R-1)
P(R-2)=1/(R-2)
...
P(2)=1/2
P(1)=1

于是乎，碰到第一个'x'就取，碰到第二个就以1/2的概率去取（若概率发生，就更新当前的'x'的位置），
...第R个'x'就以1/R的概率去取，于是乎完成操作。

优势：遍历一遍
缺陷：每碰到一个指定的字符都需要产生相应的随机数（产生等概率的随机数的最高效的算法是什么呢？）

注意了：对于一个文本流，在该流没有流完之前，你不知道该流总共有多少个字符，你也不知道总共有多少个指定的字符，并且只流一次（不会再流一次），因此，方法一和方法三都不行不通。