题目描述

官方描述(中文)
2021/08/30每日一题

思路

说实话看到题，我毫无思路。。。只能去翻一下官方题解，官方题解。官方题解使用到了好几个非常不常用的stl类（至少对于我来说非常不常用，基本没用过。。。）：

1. mt19937 随机数类
2. uniform_int_distribution均匀离散分布类
3. random_device 随机数类

还有几个不常用的函数

1. accumulate 求取指定范围的数据和
2. partial_sum 求取指定范围的前缀和放入指定容器
3. lower_bound 某一数在指定范围中第一个大于等于这个数的位置

代码

直接扣的官方代码

class Solution 
{
private:
    mt19937 gen;
    uniform_int_distribution<int> dis;
    vector<int> pre;

public:
     /*
     partial_sum() 可以计算输入序列中元素的部分和，并将结果保存到一个输出序列中
     back_inserter 是iterator适配器，它使得元素被插入到作为实参的某种容器的尾部
     random_device提供()操作符,用来返回一个min()到max()之间的一个数字
     */
    //给随机数gen设置随机种子，accumulate求取w中所有数字的和，dis为0-sum(w)的均匀离散分布
    Solution(vector<int>& w): gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0)) 
    {
        //求取w的前缀和并将结果存储在pre中
        partial_sum(w.begin(), w.end(), back_inserter(pre));
    }
    
    int pickIndex() 
    {
        //得到0-sum(w)之间的随机数
        int x = dis(gen);
        //得到随机数x在pre中的位置
        return lower_bound(pre.begin(), pre.end(), x) - pre.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

Q.E.D.