java - 从每个元素具有特定概率的数组中随机选择一个元素

Question

我希望从数组中随机选择元素，其中每个元素都有特定的被选中概率。有没有一种有效的方法可以做到这一点，或者可能是 Java 中内置的东西已经可以做到这一点？

Answer 1

O(log(n)) 方法(这是直接从 answer to a very similar question 中提取的):

通常的技术是将数组转换为累加和数组:

 [10 60 5 25]  --> [10 70 75 100]

在从零到累计总数的范围内选择一个随机数(在示例中:0 <= x < 100)。然后，使用 bisection在累积数组上将索引定位到原始数组中:

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25 

例如，如果随机变量 x 为 4，则将累积数组二等分得到的位置索引为 0，对应于原始数组中的 10。

并且，如果随机变量 x 为 72，则将累积数组二等分得到的位置索引为 2，对应于原始数组中的 5。