🟡 剑指 Offer II 071. 按权重生成随机数

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

class Solution {    private int[] prefix;    private int sum;
    public Solution(int[] w) {        int n = w.length;        sum = 0;        prefix = new int[n];        for (int i=0; i<n; i++) {            sum += w[i];            prefix[i] = sum;        }    }        public int pickIndex() {        int target = (int)(Math.random() * this.sum) + 1;        int lo=0, hi = prefix.length-1, mid, midw;        while (lo < hi) {            mid = (lo+hi) / 2;            midw = prefix[mid];            if (midw == target) {                return mid;            }            if (midw < target) {                lo = mid + 1;            } else {                hi = mid;            }        }        return lo;    }}
/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(w); * int param_1 = obj.pickIndex(); */