> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/sui-ji-shu/528.-random-pick-with-weight.md).

# 528. Random Pick with Weight

根据给定的weight生成随机数。把weight看作数量，然后直接调用rand()%总数即可。但空间消耗很大，实际上并不需要真的去根据weight生成相应数目的元素，需要的只是每个元素对应的range，然后根据随机出来的数看落在了哪个range。因此用一个数组累加记录下range，二分法找随机选出来元素对应的range上边界。

```cpp
/*
 * @lc app=leetcode id=528 lang=cpp
 *
 * [528] Random Pick with Weight
 */

// @lc code=start
class Solution {
    vector<int> elems;
public:
    Solution(vector<int>& w) {
        elems.resize(w.size());
        for (int i = 0, c = 0; i < w.size(); ++i) {
            c += w[i]; 
            elems[i] = c;
        }
    }
    
    int pickIndex() {
        int i = rand() % elems.back();
        return upper_bound(elems.begin(), elems.end(), i) - elems.begin();
    }
};

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


```