C++ 不常用的奇淫巧计

leetcode-剑指offerII 071.按权重生成随机数

给定一个正整数数组 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) 。

/*
mt19937：一种随机数生成算法
uniform_int_distribution：均匀分布
accumulate()：累加求和
partial_sum：求前缀和
back_inserter()：插入到容器后面
lower_bound()：查找下界
*/class Solution{
private:mt19937 gen;uniform_int_distribution<int> dis;vector<int> pre;
public:Solution(vector<int>& w):gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0)){partial_sum(w.begin(), w.end(), back_inserter(pre));}int pickIndex(){int x = dis(gen);return lower_bound(pre.begin(), pre.end(), x) - pre.begin();}
}