528. Randomly selected according to weight

😀 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions! 🩲 warehouse address: a daily series

Title description:

Given an array of positive integers w, where w[I] represents the weight of subscript I (subscripts start at 0), write a function pickIndex that randomly picks subscript I with a probability that is proportional to w[I].

For example, for w = [1, 3], the probability of choosing subscript 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), while the probability of choosing subscript 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

In other words, the probability of picking subscript I is w[I] / sum(w).

Example 1:

Input: ["Solution","pickIndex"] [[[1]] output: [null,0] explanation: Solution Solution = new Solution([1]); solution.pickIndex(); // Return 0, since there is only one element in the array, the only option is to return the index 0.Copy the code

Example 2:

Input: [" Solution ", "pickIndex", "pickIndex", "pickIndex", "pickIndex", "pickIndex"] [[[1, 3]], [], [], [], [], []] output: [null,1,1,1,1,0] [null,1,1,1, 0] solution.pickIndex(); // Returns 1, returns subscript 1 with probability 3/4. solution.pickIndex(); // Return 1 solution.pickindex (); // Return 1 solution.pickindex (); // Return 1 solution.pickindex (); // Returns 0, returns subscript 0 with probability 1/4. Since this is a random question, allowing for multiple answers, the following output can be considered correct: [null, 1,1,1,1,0] [null, 1,1,1,1,1] [null, 1,1,1,0,0] [null, 1,1,1,0,1] [null, 1,0,1,0,0]... So on.Copy the code

Answer:

C + + :

Rand ()%num. Back () is not an equal number. Rand ()%num. Back () is not an equal number.

class Solution {
public:
    mt19937 gen;
    vector<int> Probability;
    uniform_int_distribution<int> dis;
    // Use a random number generator
    Solution(vector<int>& w):dis(1.accumulate(w.begin(), w.end(), 0)) {
        partial_sum(w.begin(), w.end(), back_inserter(Probability));
    }
    
    int pickIndex(a) {
       
        int num=0;
        num= dis(gen);
        auto pos=lower_bound(Probability.begin(), Probability.end(), num);
        return pos-Probability.begin(a);//return -1;}};Copy the code