按权重生成随机数思路二分+前缀和

59 阅读 0 评论 39 点赞

我是靠谱客的博主自由薯片，最近开发中收集的这篇文章主要介绍按权重生成随机数思路二分+前缀和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路二分+前缀和

题目链接
题目大意，输入一个随机数，按数组下标的值比上数组和作为概率返回下标

数组并非有序，可以重复

以权重数组 [1, 2, 3, 4] 为例，那么选择下标 0 的概率为 10% (1/10)，选择下标 1 、2 和 3 的概率一次为 20% 、30% 和40%。考虑如何根据权重比例随机选择一个下标，先按等概率生成 1 ~ 10，则每个数字的概率的都为 10%。如果生成 1 则选择下标 0，概率为 10%；如果生成 2 或 3 则选择下标 1，概率为 20%；如果生成 4、5 或 6 则选择下标 2，概率为 30%；如果生成 7、8、9 或 10 则选择下标 3，概率为 40%。

先说官方题解；第一次看真的懵逼

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();
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/random-pick-with-weight/solution/an-quan-zhong-sui-ji-xuan-ze-by-leetcode-h13t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

mt19937头文件是<random> 是伪随机数产生器，用于产生高性能的随机数
uniform_int_distribution 头文件在<random>中，是一个随机数分布类，参数为生成随机数的类型，构造函数接受两个值表示区间段
accumulate 头文件在<numeric>中，求特定范围内所有元素的和。
partial_sum函数的头文件在<numeric>，对(first, last)内的元素逐个求累计和，放在result容器内
back_inserter函数头文件<iterator>，用于在末尾插入元素。
lower_bound头文件在<algorithm>，用于找出范围内不小于num的第一个元素对应迭代器

random_device是一个真随机数发生器，与mt19937配合产生一个真随机数；partial_sum()可以计算数组部分元素和，保存在一个数组中，partial_sum(容器要计算的起始位置，容器要计算的结束位置，结果存放的起始位置),back_inserter(pre)就是通过此迭代器赋值会调用push_back添加元素到容器 pre。
不知道这些头文件包含直接 #include <bits/stdc++.h>

自己如果手动实现，如下代码

class Solution {
vector<int> add_vector;
int len;
public:
Solution(vector<int>& w) {
len=w.size();
add_vector.resize(len+1);
add_vector[0]=0;
for(int i=1;i<len+1;i++){
add_vector[i]=w[i-1]+add_vector[i-1];
}
}
int pickIndex() {
int pick=rand()%add_vector[len]+1;//在前缀和数组中选择
// 在闭区间 [1, add_vector[n - 1]] 中随机选择一个数字
//对应每个概率相等，但对应下标范围不同
return getLeft(pick , add_vector)-1;
}
//左闭右开二分查找左边界
int getLeft(int target, vector<int>& w){
int right=w.size();
int left=0;
while(left<right){
int mid = left+(right-left)/2;
if(w[mid]==target){
right=mid;
}else if(w[mid]<target){
left=mid+1;
}else if(w[mid]>target){
right=mid;
}
}
if(left<0) return -1;
return left;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(w);
* int param_1 = obj->pickIndex();
*/