Random Pick with Weight

medium 原题链接：https://leetcode.com/problems/random-pick-with-weight/

Random Pick with Weight

原题链接：https://leetcode.com/problems/random-pick-with-weight/

描述

You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed).

We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).

More formally, the probability of picking index i is w[i] / sum(w).

例子

Input ：

["Solution","pickIndex"]

[[[1]],[]]

Output ：

[null,0]

Explanation ：

Solution solution = new Solution([1]);

solution.pickIndex();

// return 0. Since there is only one single element on the array the only option is to return the first element.

题意解释

the array of {1, 3, 4, 6}

the pickIndex() call will have

1/(1+3+4+6) = 1/14 = ~7% chance of picking index 0;

3/14 = 21% change of picking index 1;

4/14 = 29% change of picking index 2;

and 6/14 = 43% of picking index 3.

解法一

binary search

class Solution {
    public:
    vector<int> s;
    Solution(vector<int>& w) {
        for (int ind : w){
            if(s.empty())
                s.push_back(ind);
            else
                s.push_back(ind + s.back());
        }
    }
    
    int pickIndex() {
        int x = s.back();
        int index = rand() % x;
        auto it = upper_bound(s.begin(), s.end(),index);
        return it - s.begin();
    }
};

总结