[leetcode daily question 2021/8/30]528. Choose randomly by weight [medium]

The title comes from leetcode, Solutions and ideas represent only personal views . Portal .
difficulty ： secondary
Time ：30min
TAG： The prefix and , randomization

subject

Given an array of positive integers w , among w[i] Subscript subscript i The weight of （ Subscript from 0 Start ）, Please write a function pickIndex , It can randomly take subscripts i, Select subscript i The probabilities of and w[i] In direct proportion to .

for example , about w = [1, 3], Select subscripts 0 The probability of is 1 / (1 + 3) = 0.25 （ namely ,25%）, And choose subscript 1 The probability of is 3 / (1 + 3) = 0.75（ namely ,75%）.

in other words , Select subscript i The probability of is w[i] / sum(w) .

Example 1：

 Input ：
["Solution","pickIndex"]
[[[1]],[]]
 Output ：
[null,0]
 explain ：
Solution solution = new Solution([1]);
solution.pickIndex(); //  return  0, Because there is only one element in the array , So the only option is to return the subscript  0.

Example 2：

 Input ：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
 Output ：
[null,1,1,1,1,0]
 explain ：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); //  return  1, Returns the subscript  1, Return the subscript probability as  3/4 .
solution.pickIndex(); //  return  1
solution.pickIndex(); //  return  1
solution.pickIndex(); //  return  1
solution.pickIndex(); //  return  0, Returns the subscript  0, Return the subscript probability as  1/4 .

 Because it's a random problem , Allow multiple answers , So the following outputs 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]
......
 and so on .

Tips ：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10⁵
• pickIndex Will be called no more than 10000 Time

Ideas

utilize w Calculation , Every index Should be selected 【 Probability array p】

Think about the key to solving this problem , It only needs When the number of calls is large enough , return index Probability of compliance 【 Probability array p】 that will do .

Every call changes , In the current situation ,index The probability of being selected . namely , In code nums An array with the total. utilize nums[index]/total, You can calculate , In the current situation ,index The probability of being selected .

What we need to do is , Maintain a nums Array , bring nums[i]/total Approximately equal to p[i].

Answer key

class Solution {
    
public:
    vector<double> p;
    double total = 0 + 1e-7;
    vector<int> nums;
    int n = 0;
    Solution(vector<int>& w) {
    
        int n = w.size();
        this->n = n;
        p.resize(n);
        double sum = 0;
        for(int i=0;i<n;i++){
    
            sum += w[i];
        }
        for(int i=0;i<n;i++){
    
            p[i] = w[i] / sum;
        }
        nums.resize(n);
    }
    int pickIndex() {
    
        // Take a random number 
        int index = rand() % n;
        while(nums[index]/total >= p[index]){
    
            index = rand() % n;
        }
        nums[index]++;
        total++;
        return index;
    }
};

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

Algorithm complexity

Time complexity ： Initialize array $O(n)$, Each choice $O({\sum }_i^n{w}_i)$.
Spatial complexity ：$O(n)$. Probability array p, Count array nums.

---

The time to initialize the array is easy to calculate , Time selected each time , My thoughts are as follows .

nums = [1,1,1], total = 3, w=[2,2,2], p=[1/3,1/3,1/3]

at present ,nums[i]/total Is in accordance with p[i] Of .
that , With total An increase in , The next time nums[i]/total accord with p[i] when ,total The smallest case is ？
Should be nums = [2,2,2], That is, everyone increases 1 individual .total increase 3.

---

 Then if ,
nums = [1,2,1], total = 4, w=[1,2,1], p=[1/4,1/2,1/4]

that , With total An increase in , The next time nums[i]/total accord with p[i] when ,total The smallest case is ？
Should be nums = [2,4,2], That is to say total increase 4.

---

 Then if ,
nums = [2,4,2], total = 8, w=[1,2,1], p=[1/4,1/2,1/4]

that , With total An increase in , The next time nums[i]/total accord with p[i] when ,total The smallest case is ？
Should be nums = [3,6,9], instead of nums = [4,8,4],total increase 4.

---

 Then if ,
nums = [1,2,1], total = 4, w=[2,4,2], p=[1/4,1/2,1/4]

that , With total An increase in , The next time nums[i]/total accord with p[i] when ,total The smallest case is ？
Should be nums = [2,4,2], instead of nums = [3,6,9], That is to say total increase 4, instead of 8.

---

therefore , In each sampling , Each time it reaches the next state (nums[i]/total accord with p[i]),total It should increase （ Less than ）${\sum }_i^n{w}_i$ Time .

Why less than ？
because ,total What should be added is ,w Zhongba Common divisor The accumulated value after reduction .

---