Leetcode 528 按权重随机选择

本文主要是介绍Leetcode 528 按权重随机选择，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目信息

LeetoCode地址: . - 力扣（LeetCode）

题目理解

想象题目提供的w数组里是很多根长短不一的棍子，然后我们将其按顺序排列成一条线。

然后我们扔一个沙包，砸中哪一根棍子，就代表命中了那根棍子代表的数字。很显然，棍子越长，就越容易砸中。

假如这五根棍子分别长1，2，3，4，5，那么合并后总长度就是1+2+3+4+5=15

那么沙包扔出后可能会落在0到15之间的任何一个位置。具体来说，落到[0,1]的可能性会比落到[1,3]小，因为后者代表的区间更大，而概率最大的则是[10,15],这代表了最后一根棍子的区间。

那么题目就变成了，如何快速找到沙包落点属于哪一个区间。使用前缀和，我们可以很轻松的表示这5根棍子的区间:[1,3,6,10,15]，而这又恰巧是一个单调递增数组，使用二分法，可以在O(logn)的时间复杂度内找到区间。

前缀和+二分写法

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