关于leetcode算法:彩票调度算法

leetcode 528. 按权重随机抉择

给你一个下标从 0 开始 的正整数数组 w，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex，它能够随机地从范畴 [0, w.length – 1] 内（含 0 和
w.length – 1）选出并返回一个下标。选取下标 i 的概率 为 w[i] / sum(w)。

例如，对于 w = [1, 3]，筛选下标 0 的概率为 1 / (1 + 3) = 0.25（即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

rand()

Generate random number
Returns a pseudo-random integral number in the range between 0 and RAND_MAX.

rand() % n 产生范畴为 [0, n) 中的随机数。

举例剖析

假如给定数组 w =[1, 2, 3]。筛选下标 0 的概率为 1/(1+2+3)=1/6，而选取下标 1 的概率为 2 /(1+2+3)=2/6，选取下标 2 的概率为 3 /6。

应用线段长度示意下标 0、1 和 2 呈现的概率，如下图所示：

(0, 6]区间总长为 6，那么取 (0, 6] 范畴内的随机数，该随机数落在 (0,1]、(1,3] 和(3,6]区间内的概率别离为 1 /6、2/ 6 和 3 /6，即满足权值概率要求。
其中，区间分段点 1、3、6 即为前缀和。

此处咱们能够仅思考随机数为整数的状况：(0, 6]区间内随机数为 1 属于(0,1]；2、3 属于(1,3]；4、5、6 属于(3,6]。

随机产生一个数字，而后应用二分法查找>= 该数的最小值在前缀和中的地位，即为下标。

代码

class Solution {
public:
    vector<int> s;
    Solution(vector<int>& w) {
        s = w;
        int n = w.size();
        for (int i = 1; i < n; i++) s[i] += s[i - 1];
    }
    
    int pickIndex() {int x = rand() % s.back() + 1; // 随机数范畴[1...s.back()]
        return lower_bound(s.begin(), s.end(), x) - s.begin();}
};

利用场景

彩票调度算法[操作系统]
https://pages.cs.wisc.edu/~re…