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();
}
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码