lea*_*ner 3 random algorithm math
设计一个快速算法,从离散分布中重复生成数字:给定一个数组a []的非负实数,总和为1,目标是以概率a [i]返回索引i
我在一本在线算法书"Java编程入门",第4.2章:排序和搜索(http://introcs.cs.princeton.edu/java/42sort/)中找到了这个问题.
提示说:
形成累积和的数组s [],使得s [i]是[]的前i个元素的总和.现在,生成0到1之间的随机实数r,并使用二进制搜索返回索引i,其中s [i]≤s[i + 1].
一些我怎么不能理解提示,因此无法找到解决方案..