528. 按权重随机选择

528. 按权重随机选择

把权重分成长度

class Solution {
public:
    Solution(vector<int>& w) : ww(w), total(0) {
        int end = 0;
        sz = w.size();
        for(auto& num : ww)
        {
            total += num;
            num = end;
            end = total;
        }
        u = uniform_int_distribution<int>(0, total - 1);
    }
    
    int pickIndex() {
        int pick = u(e);
        int lo = 0, hi = sz - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2 + 1;
            if(ww[mid] > pick)
                hi = mid - 1;
            else
                lo = mid;
        }
        return hi;
    }
private:
    vector<int> ww;
    int sz;
    int total;
    mt19937 e;
    // default_random_engine e;
    uniform_int_distribution<int> u;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

使用STL的版本

右开左闭

class Solution {
public:
    Solution(vector<int>& w) : e(random_device{}()), u(0, accumulate(w.begin(), w.end(), 0) - 1) {
        partial_sum(w.begin(), w.end(), back_inserter(pre));
    }
    
    int pickIndex() {
        int x = u(e);
        return upper_bound(pre.begin(), pre.end(), x) - pre.begin();
    }
private:
    mt19937 e;
    uniform_int_distribution<int> u;
    vector<int> pre;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

或

右闭左开

class Solution {
public:
    Solution(vector<int>& w) : e(random_device{}()), u(1, accumulate(w.begin(), w.end(), 0)) {
        partial_sum(w.begin(), w.end(), back_inserter(pre));
    }
    
    int pickIndex() {
        int x = u(e);
        return lower_bound(pre.begin(), pre.end(), x) - pre.begin();
    }
private:
    mt19937 e;
    uniform_int_distribution<int> u;
    vector<int> pre;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

C++STL说明：

1. mt19937头文件是 是伪随机数产生器，用于产生高性能的随机数
2. uniform_int_distribution 头文件在中，是一个随机数分布类，参数为生成随机数的类型，构造函数接受两个值表示区间段
3. accumulate 头文件在中，求特定范围内所有元素的和。
4. spartial_sum函数的头文件在，对(first, last)内的元素逐个求累计和，放在result容器内
5. back_inserter函数头文件，用于在末尾插入元素。
6. lower_bound头文件在，用于找出范围内不大于num的第一个元素
7. upper_bound头文件在，用于找出范围内大于num的第一个元素
8. random_device头文件再，是非确定性随机数生成器，生成均匀分布的无符号数。生成器可能会依靠非确定源（比如硬件设备）生成真随机数，不过在环境受限时生成伪随机数。