JZTXT

【二分查找】LeetCode 528. 按权重随机选择

发布时间 2023-05-07 09:12:38作者: Frodo1124

题目链接

528. 按权重随机选择

思路

代码

class Solution {
    private int[] sum;

    public Solution(int[] w) {
        sum = new int[w.length + 1];
        for(int i = 1; i < sum.length; i++){
            sum[i] = sum[i - 1] + w[i - 1];
        }
    }

    public int pickIndex() {
        int n = sum.length;
        // 0 <= random < 1
        // => 0 <= (int)(random * sum[n - 1]) <= sum[n - 1] - 1
        // => 1 <= (int)(random * sum[n - 1]) + 1 <= sum[n - 1]
        int target = (int)(Math.random() * sum[n - 1]) + 1;
        int left = 1;
        int right = n - 1;

        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(sum[mid] == target){
                return mid - 1;
            }else if(sum[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return left - 1;
    }
}