一、题目

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

点击查看原题
难度级别： 中等

二、思路

1）前缀和+二分

整体思路是：既然权重代表了选中的概率，那么就使用数组所有元素之和sum，随机生成sum内的数字，然后根据前缀和找到对应的位置，返回位置即可（查找使用二分查找进行优化）

三、代码

1）前缀和+二分

class Solution {
    int[] pre;
    public Solution(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            pre[i] = pre[i-1] + w[i];
        }
    }
    public int pickIndex() {
        int val = (int)(Math.random()*pre[pre.length - 1]) + 1;
        return find(val);
    }
    private int find(int val) {
        int s = 0, e = pre.length;
        while (s < e) {
            int mid = (s + e)/2;
            if (pre[mid] == val) {
                return mid;
            } else if (pre[mid] < val) {
                s = mid + 1;
            } else {
                e = mid;
            }
        }
        return s;
    }
}

时间复杂度为O(logn)，空间复杂度为O(n)