力扣labuladong——一刷day25

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

带权重的随机选择算法

前言

一、力扣528. 按权重随机选择

class Solution {private int[] preSum;private Random rand = new Random();public Solution(int[] w) {preSum = new int[w.length+1];preSum[0] = 0;for(int i = 1; i <= w.length; i ++){preSum[i] = preSum[i-1] + w[i-1];}}public int pickIndex() {int n = preSum.length;int target = rand.nextInt(preSum[n-1])+1;return fun(preSum, target) - 1;}public int fun(int[] preSum, int target){int left = 0, right = preSum.length-1;while(left <= right){int mid = left + (right-left)/2;if(preSum[mid] == target){right = mid - 1;}else if(preSum[mid] < target){left = mid + 1;}else{right = mid - 1;}}return left;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(w);* int param_1 = obj.pickIndex();*/