按权重随机选择

528. 按权重随机选择

见识过很多等概率随机选择，本片文章介绍一种「按权重随机选择」

对于样例：w = [1, 2, 3, 4]

• 返回下标 0 的概率为 $\frac{1}{10}$$\frac{1}{10}$
• 返回下标 1 的概率为 $\frac{2}{10}$$\frac{2}{10}$
• 返回下标 2 的概率为 $\frac{3}{10}$$\frac{3}{10}$
• 返回下标 3 的概率为 $\frac{4}{10}$$\frac{4}{10}$

这里使用「前缀和」➕「二分搜索」。是不是觉得很莫名其妙，这和前缀和、二分搜索有什么关系，不要急，一步一步的来分析！！

关于「前缀和」的详细介绍可见 前缀和数组

关于「二分搜索」的详细介绍可见 二分搜索

关于Random的详细介绍可见 Random 类

我们需要考虑的无非就是如何才能按权重的选择，Random()返回的都是等概率的

对于样例：w = [1, 2, 3, 4]，其「前缀和数组」可视化如下：

随机生成一个区间为[1, 10]的数：

• 如果值为 1 返回下标 0
• 如果值为 2，3 返回下标 1
• 如果值为 4，5，6 返回下标 2
• 如果值为 7，8，9，10 返回下标 3

刚好上述权重和最初分析的概率是等价的！！

对于target = 5，返回一个大于等于 5 的最小下标，即为 2

注意：preSum[]相对于原数组整体向右偏移了一位

下面给出完整代码：

class Solution {
    private int[] preSum;
    private Random random;
    public Solution(int[] w) {
        random = new Random();
        preSum = new int[w.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + w[i - 1];
        }
    }
    
    public int pickIndex() {
        int target = random.nextInt(preSum[preSum.length - 1]) + 1;
        int l = 1, r = preSum.length - 1;
        while (l <= r) {
            int mid = l - (l - r) / 2;
            if (target <= preSum[mid]) r = mid - 1;
            else l = mid + 1;
        }
        // 由于前缀和数组向右偏移了一位
        return l - 1;
    }
}