非均匀随机数生成替代方案的可行性与效率问询

问题背景 #

这个问题出自《编程面试元素》5.16：

给定n个数字以及和为1的概率p0, p1,.., pn-1，现有可生成[0,1]区间均匀随机数的生成器，如何按指定概率生成这n个数字中的一个。

举个实际例子：

若数字为3、5、7、11，概率为9/18, 6/18, 2/18, 1/18，则调用程序1000000次时，3应出现约500000次，7约111111次等。

书中的标准解法 #

书中给出的思路是构建累积概率区间：计算p0, p0+p1, p0+p1+p2,...这类累积值，对应上面的例子，区间就是[0.0, 0.5), [0.5, 0.8333), ...。把这些端点整理成有序数组（比如示例里的[1/18, 3/18, 9/18, 18/18]）。生成随机数后，找到第一个大于该随机数的端点，它的索引就对应要输出的数字的索引。

• 预处理复杂度：O(N)
• 查询复杂度：O(log N)

我的思路与疑问 #

我琢磨出了一种预处理复杂度O(N)、查询复杂度*O(1)*的替代方案：遍历每个数字，把数字重复100 * 对应概率次（比如数字3就重复(9/18)*100 = 50次），最后拼成一个刚好100个元素的列表——元素的重复次数完全对应它的出现概率。之后生成一个[0,1)的随机数，乘以100取整得到索引，直接从列表里拿值就行。

我想请教大家：这个方案有没有什么隐藏的问题？它真的比书中的方案更高效吗？

内容的提问来源于stack exchange，提问作者segue_segway