按权重随机选择

528. 按权重随机选择 (Medium)

给定一个正整数数组 w ,其中 w[i] 代表位置 i 的权重,请写一个函数 pickIndex ,它可以随机地获取位置 i,选取位置 i 的概率与 w[i] 成正比。

说明:

  1. 1 <= w.length <= 10000
  2. 1 <= w[i] <= 10^5
  3. pickIndex 将被调用不超过 10000 次

示例1:

输入: 
["Solution","pickIndex"]
[[[1]],[]]
输出: [null,0]

示例2:

输入: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出: [null,0,1,1,1,0]

输入语法说明:

输入是两个列表:调用成员函数名和调用的参数。Solution 的构造函数有一个参数,即数组 wpickIndex 没有参数。输入参数是一个列表,即使参数为空,也会输入一个 [] 空列表。

相关话题

[二分查找] [Random]

相似题目

  1. 随机数索引 (Medium)
  2. 黑名单中的随机数 (Hard)
  3. 非重叠矩形中的随机点 (Medium)

解法