[leetcode每日一题2021/8/30]528. 按权重随机选择【中等】

题目来源于leetcode，解法和思路仅代表个人观点。传送门。
难度：中等
时间：30min
TAG：前缀和，随机化

题目

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[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]
......
诸若此类。

提示：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10⁵
• pickIndex 将被调用不超过 10000 次

思路

利用w计算，每个index应该被选取的【概率数组p】

思考本题解题关键，只需要在调用次数足够大的时候，返回index的概率符合【概率数组p】即可。

每次调用都会改变，当前情况下，index被选中的概率。即，代码中的nums数组与total。利用nums[index]/total，即可计算，当前情况下，index被选中的概率。

我们需要做得就是，维护一个nums数组，使得nums[i]/total近似等于p[i]。

题解

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() {
    
        //随机取一个数
        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(); */

算法复杂度

时间复杂度： 初始化数组$O(n)$，每次选择$O({\sum }_i^n{w}_i)$。
空间复杂度：$O(n)$。概率数组p，计数数组nums。

---

初始化数组的时间容易计算，每次选择的时间，我的思考如下。

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

目前，nums[i]/total 是符合 p[i] 的。
那么，随着total的增加，下一次 nums[i]/total 符合 p[i] 时，total最小的情况是？
应该是 nums = [2,2,2]，也就是每位都增加1个。total增加3。

---

那如果，
nums = [1,2,1], total = 4, w=[1,2,1], p=[1/4,1/2,1/4]

那么，随着total的增加，下一次 nums[i]/total 符合 p[i] 时，total最小的情况是？
应该是nums = [2,4,2]，也就是total增加4。

---

那如果，
nums = [2,4,2], total = 8, w=[1,2,1], p=[1/4,1/2,1/4]

那么，随着total的增加，下一次 nums[i]/total 符合 p[i] 时，total最小的情况是？
应该是nums = [3,6,9]，而不是nums = [4,8,4]，total增加4。

---

那如果，
nums = [1,2,1], total = 4, w=[2,4,2], p=[1/4,1/2,1/4]

那么，随着total的增加，下一次 nums[i]/total 符合 p[i] 时，total最小的情况是？
应该是nums = [2,4,2]，而不是nums = [3,6,9]，也就是total增加4，而不是8。

---

所以，每次抽样中，每次到达下一个状态(nums[i]/total符合p[i])，total应该会增加（小于）${\sum }_i^n{w}_i$次。

为什么小于？
因为，total应该加上的是，w中把公约数约掉之后的累加值。

---