带权重的 random()
random() 是一个重要的函数，它会以相同的概率返回一个随机数。带权重的 random() 要求我们生成具有不同权重的随机数。
1
2
3
4
5
| 例如：A = [10, 50, 20, 20]，如果我们用 P(x) 表示返回 x 的概率，则有：
P(0) = 10 / 100 = 0.1
P(1) = 50 / 100 = 0.5
P(2) = 20 / 100 = 0.2
P(3) = 20 / 100 = 0.2
|
一种简单的方法是我们可以创建一个包含 个元素的数组。我们随机设置 个元素为 ， 个元素为 ， 个元素为 ， 个元素为 。
然后我们可以从 到 随机选择一个索引，并返回所选索引上的值。然而，上述方法有一个明显的缺点。它会消耗大量内存，设置值也会花费大量时间。
我们能否压缩这些信息，而不是创建一个数组？答案是可以的，让我们考虑大小为 的权重数组 的前缀和数组 （0索引）。
然后对于给定的数组，我们有 和 。我们可以从 中提取 个区间 。每个区间对应于权重长度。这意味着，如果我们随机选择一个索引 , 落入 的概率是.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
TreeMap<Integer, Integer> map = new TreeMap<>();
int sw = 0;
Random rng = new Random();
public Solution(int[] w) {
map.put(sw, 0);
sw += w[0];
for(int i=1;i<w.length;i++) {
map.put(sw, i);
sw += w[i];
}
}
public int pickIndex() {
int number = Math.abs(rng.nextInt()) % sw;
return map.get(map.floorKey(number));
}
}
|
洗牌算法
Fisher–Yates 洗牌算法可用于生成数组的随机排列。该算法背后的原理是我们需要确保每对索引，即 具有相同的交换概率。
1
2
3
4
5
6
7
8
9
10
11
| int[] shuffle(int[] arr) {
Random random = new Random();
int n = arr.length;
for(int i=n-1;i>0;i--) {
int j = random.nextInt() % (i + 1);
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
|
在上述实现中，对于每个 ，我们随机选择一个 进行交换。
注意，我们也包括 ，因为有可能我们根本不改变它。
通过这种方式，我们能够覆盖所有对 ，并且当我们从 到 迭代 i 时，我们将能够覆盖所有对。