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
分享
二维码
< <上一篇

)">
下一篇>>