LeetCode528 按权重随机选择

发表于 | 分类于 |
字数统计: 218 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/random-pick-with-weight/description/

题面

给定一个数组，数组每个位置的值表示该位置的权重，要求按照权重的概率去随机采样。

解法

我们可以先使用 partial_sum 求前缀和，这个结果对于正整数数组是单调递增的。每当需要采样时，我们可以先随机产生一个数字，然后使用二分法查找其在前缀和中的位置，以模拟加权采样的过程。

用前缀和解决权重随机的问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> pre;

    Solution(vector<int>& w): pre(move(w)) {
        // pre.resize(w.size());
        // pre[0] = w[0];
        // for (int i = 1; i < w.size(); i++) {
        //     pre[i] = pre[i - 1] + w[i];
        // }
        partial_sum(pre.begin(), pre.end(), pre.begin());
    }
    
    int pickIndex() {
        int target = rand() % pre.back() + 1;
        return lower_bound(pre.begin(), pre.end(), target) - pre.begin();

    }
};