0528. Random Pick with Weight
=============================
题目信息
--------
:题号: 0528
:难度: Medium
:主题: 权重数组、随机下标、概率比例、对象调用
:原题: `LeetCode 0528 `_
:重点: 返回零基下标、每个下标概率等于其权重占总权重的比例、重复调用相互独立
题目重述
--------
使用正整数数组 ``w`` 初始化一个对象。每次调用 ``pickIndex()`` 时,随机返回一个零基下标 ``i``,其被选中的概率应为 ``w[i] / sum(w)``。
所有权重都为正,因此每个下标都有非零概率。概率按下标而不是按权重值分组;即使两个位置权重相同,它们仍是两个独立结果。对象在多次调用中保持同一组权重。
自建示例
--------
三个下标具有不同概率:
.. code-block:: text
输入:w = [1,3,2]
输出:pickIndex() 可返回 0、1 或 2
解释:总权重为 6,三个下标的返回概率分别为 1/6、1/2 和 1/3。
相同权重等概率:
.. code-block:: text
输入:w = [4,4]
输出:pickIndex() 返回 0 或 1
解释:两个下标各占总权重的一半,因此概率均为 1/2。
前缀权重把概率变成整数区间
--------------------------
把权重累加成前缀和,例如 ``[1,3,2]`` 对应区间 ``[1]``、``[2..4]``、``[5..6]``。在 ``1..total`` 中均匀抽取一个整数,再用 ``lower_bound`` 找到第一个前缀和不小于它的下标;第 ``i`` 个下标恰好占有 ``w[i]`` 个整数。
权重只在构造时建立,后续调用不改变前缀数组,随机抽取彼此独立。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::vector prefix;
std::mt19937 generator{std::random_device{}()};
public:
Solution(std::vector& w) {
long long total = 0;
for (int weight : w) {
total += weight;
prefix.push_back(total);
}
}
int pickIndex() {
std::uniform_int_distribution distribution(
1, prefix.back());
long long value = distribution(generator);
return static_cast(std::lower_bound(
prefix.begin(), prefix.end(), value) - prefix.begin());
}
};
代码分析
--------
前缀区间长度与权重一一对应,均匀抽取整数后落入下标 ``i`` 的概率为 ``w[i]/total``。构造时间和空间复杂度为 ``O(n)``,每次查询二分耗时 ``O(log n)``,额外查询空间为 ``O(1)``。