网站后台seo设置,外国人做美食视频网站,自己做网站排名,云南省新农村建设网站文章目录1. 题目2. 解题1. 题目
给定一个正整数数组 w #xff0c;其中 w[i] 代表下标 i 的权重#xff08;下标从 0 开始#xff09;#xff0c;请写一个函数 pickIndex #xff0c;它可以随机地获取下标 i#xff0c;选取下标 i 的概率与 w[i] 成正比。
例如#xf…
文章目录1. 题目2. 解题1. 题目
给定一个正整数数组 w 其中 w[i] 代表下标 i 的权重下标从 0 开始请写一个函数 pickIndex 它可以随机地获取下标 i选取下标 i 的概率与 w[i] 成正比。
例如对于 w [1, 3]挑选下标 0 的概率为 1 / (1 3) 0.25 即25% 而选取下标 1 的概率为 3 / (1 3) 0.75即75%。
也就是说选取下标 i 的概率为 w[i] / sum(w) 。
示例 1
输入
[Solution,pickIndex]
[[[1]],[]]
输出
[null,0]
解释
Solution solution new Solution([1]);
solution.pickIndex();
// 返回 0因为数组中只有一个元素所以唯一的选择是返回下标 0。示例 2
输入
[Solution,pickIndex,pickIndex,pickIndex,pickIndex,pickIndex]
[[[1,3]],[],[],[],[],[]]
输出
[null,1,1,1,1,0]
解释
Solution solution new Solution([1, 3]);
solution.pickIndex(); // 返回 1返回下标 1返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0返回下标 0返回该下标概率为 1/4 。由于这是一个随机问题允许多个答案
因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。提示
1 w.length 10000
1 w[i] 10^5
pickIndex 将被调用不超过 10000 次来源力扣LeetCode 链接https://leetcode-cn.com/problems/random-pick-with-weight 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 497. 非重叠矩形中的随机点前缀和二分查找
计算前缀和权重随机权值二分查找找到权值落在的区间点
class Solution {vectorint w_presum;int total;
public:Solution(vectorint w) {w_presum w;for(int i 1; i w.size(); i)w_presum[i] w_presum[i-1];total w_presum.back();}int pickIndex() {int w rand()%total 1;int L 0, R w_presum.size()-1, mid;while(L R){mid L((R-L)1);if(w_presum[mid] w)L mid1;else{if(mid0 || w_presum[mid-1] w)return mid;elseR mid-1;}}return -1;}
};88 ms 39.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
