528. Random Pick with Weight

https://leetcode.com/problems/random-pick-with-weight/description/

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

/*
 * @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