算法从离散分布产生随机数？
设计一个快速算法重复生成数字从 离散分布：给定一个数组[]的非负实数 该总和为1时，目标是要返回索引i的概率为A [1]
Design a fast algorithm to repeatedly generate numbers from the discrete distribution: Given an array a[] of non negative real numbers that sum to 1, the goal is to return index i with probability a[i]
我发现这个问题在网上算法的书，介绍Java编程，章节4.2：排序和搜索（http://introcs.cs.princeton.edu/java/42sort/）
I found this question in a an online algorithm book, Introduction to Programming in Java, chapter 4.2: Sorting and Searching (http://introcs.cs.princeton.edu/java/42sort/) .
提示说：
表[]的。数组s累积款项使得S [i]为一[]的第i个元素的总和。现在，生成0和1之间的随机实数r，并使用二进制搜索返回的索引为哪些I S [I]≤S [I + 1]
Form an array s[] of cumulated sums such that s[i] is the sum of the first i elements of a[]. Now, generate a random real number r between 0 and 1, and use binary search to return the index i for which s[i] ≤ s[i+1].
一些如何，我无法理解的暗示，因此无法找到解决方案。
some how I am not able to understand the hint and hence cant find the solution..
有很多方法来回答这个问题。 本文 描述了各种不同的方法，他们的优势，他们的弱点，他们的运行时间。它总结了一个算法，需要为O（n）preprocessing时间，然后生成数字时间O（1）每个。
There are many ways to answer this problem. This article describes numerous approaches, their strengths, their weaknesses, and their runtimes. It concludes with an algorithm that takes O(n) preprocessing time, then generates numbers in time O(1) each.
您正在寻找下所描述的具体办*盘赌选择。
The particular approach you're looking for is described under "roulette wheel selection."
希望这有助于！