最朴素的想法
一开始，不会做，就想到了最简单的方法，那就是根据权重数组 $w$ 的索引值依次构建 $w[i]$ 个 $i$ 值，放入数组
nums中，然后利用随机数生成一个值randomNUm，则nums[randomNum]就是每次选出来的索引，同时也符合其概率。
- 可惜的是这样会超出内存限制
- 有没有可以减少内存使用的方法？
前缀和+二分查找
思路是根据 带权重的随机选择算法::labuladong总结的
类似于上述构建的
nums，其实某一段（假设是index1到index2）中都是相同的数字，也就是说对于随机生成的数字，假如在index1到index2之间，则返回的结果是一样的，那是不是没有必要记录所有索引的位置，只需要该索引的起始位置和结束位置就可以了，前缀和可以做到这些。
前缀和
假设权重数组 $w[4]={2,3,1,2}$，则在朴素想法中，生成的
nums数组应该是nums[]={0,0,1,1,1,2,3,3}，这样对于[0-nums.size()-1]的随机数选出来的结果是符合其权重的。其实可以发现，$0\sim 1$ 都是输出索引 $0$，$2\sim 4$ 都是输出索引 $1$，依次类推……
- 也就是说，随机数字在某个区间对应着索引值
- 因此记录一个前缀和数组，数组内容就是记录着每个索引值的边界位置，对应于上述例子，
preSum[]={2,5,6,8}（就是由权重数组得来），因此随机数的范围应该是1-8之间。 - 注意：前缀和数组记录的是索引相对应的边界位置，如果找到，直接返回对应索引即可，但如果生成的随机数不在前缀和数组中，应该如何返回值呢？
- 其实也很简单，类似于力扣的 35. 搜索插入位置，举个栗子：如果随机数是3，应该返回5的索引位置，类似于其插入位置，只不过随机数一定是在
preSum的范围内，这是与 35. 搜索插入位置 不同的。
二分查找
在前缀和部分，其实已经说明了二分查找位置的方法，几乎和 35. 搜索插入位置 一样。
- 参考 35. 搜索插入位置 写的 题解
贴个代码
class Solution {
public:
Solution(vector<int>& w) {
int n=w.size();
preSum.resize(n); // 大小和权重数组一样
// 构造前缀和数组
preSum[0]=w[0];
for(int i=1;i<n;i++)
{
preSum[i]=preSum[i-1]+w[i];
}
}
int pickIndex() {
// 根据前缀和来找出，随机数字的位置
// 因为权重数组是大于等于1的，因此只需要生成[1,preSum[end]]范围的数字即可
int n=preSum.size();
int target=rand()%preSum[n-1]+1;
// 接下来就是找这个随机数字所在的区间或者说索引
// 采用二分法查找，如果preSum中存在这个随机数字，则说明它刚好在右边界位置
// 因此如果找不到这个随机数字，则应该返回大于它的数的索引，或者说类似于35.搜索插入位置题
int left=0,right=n-1;
// 类似于LeetCode 35题写法
while(left<right)
{
int mid=left+(right-left)/2;
if(preSum[mid]==target)
return mid;
else if(preSum[mid]>target)
right=mid-1;
else
left=mid+1;
}
// 结束条件：left=right，注意left索引值还没有进行过比较
if(preSum[left]==target)
return left;
// 因为升序排列
else if(preSum[left]<target)
return left+1;
else if(preSum[left]>target)
return left;
return -1;
}
private:
vector<int> preSum;
};$\cdots$ end $\cdots$