528-random-pick-with-weight.md

528. Random Pick with Weight - 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

说明:

1. 1 <= w.length <= 10000
2. 1 <= w[i] <= 10^5
3. pickIndex 将被调用不超过 10000 次

示例1:

输入: 
["Solution","pickIndex"]
[[[1]],[]]
输出: [null,0]

示例2:

输入: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出: [null,0,1,1,1,0]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

---

题目标签：Binary Search / Random

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	67 ms	48.3 MB

class Solution {

    private int[] w;
    private int[] s;
    public Solution(int[] w) {
        this.w = w;
        s = w;
        int tmp = 0;
        for (int i = 0; i < w.length; i++) {
            tmp += w[i];
            s[i] = tmp;
        }
    }

    public int pickIndex() {
        int t = (int)(Math.random() * s[s.length - 1]) + 1;
        int l = 0, r = s.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (s[mid] >= t) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */