题目链接
思路
代码
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;
}
}
标签:二分,int,sum,mid,length,随机,528,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17378881.html