528. Random Pick with Weight

思路：

1. 将weight理解为重复次数，比如

(0, 3), (1, 2), (2, 1)

可以看做

0 0 0 1 1 2

这样在上述数组中随机抽取一个数的概率将与他们出现的频次对应。

2. 用presum表示位置
3. 用binary search搜索位置得到对应的数。

class Solution {
private:
    vector<int> presum;
    int base; // total, sum(w)
public:
    Solution(vector<int>& w) {
        int n = w.size();
        presum = vector<int>(n, 0);
        presum[0] = w[0];
        //index 0: [1, presum[0]]
        //index i: [presum[i-1] + 1, presum[i]]
        for(int i = 1; i < n; i++)
            presum[i] = presum[i - 1] + w[i];
        base = presum.back();
    }
    
    int pickIndex() {
        // based on count, so idx start from 1
        // idx: [1, base]
        int idx = rand() % base + 1;
        int lo = 0, hi = presum.size() - 1;
        while(lo < hi){
            int mid = lo + (hi - lo) / 2;
            if(presum[mid] == idx)
                return mid;
            if(presum[mid] < idx)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
};

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