LeetCode刷题【528】按权重随机选择

给定一个正整数数组 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^5
• pickIndex 将被调用不超过 10000 次

题解

8月30日 每日一题

class Solution {

    int[] preSum;
    public Solution(int[] w) {
        for (int i = 1; i < w.length; i++) {
            w[i] = w[i]+w[i-1];
        }
        preSum = w;
    }
    
    public int pickIndex() {
        int randNum = (int)(Math.random() * preSum[preSum.length-1])+1;
        int left = 0;
        int right = preSum.length-1;
        while (left < right){
            int mid = (left + right) >> 1;
            if (preSum[mid] < randNum){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        System.out.println(left);
        return left;
    }
}

大致思路，比如数组[1,2,3]，要求值对应概率的话，最直观的就会想到创建一个集合，里面放入1个“1”，放入两个“2”，方式3个“3”，然后随机取一个值，这个取到的概率满足1的几率是1/6，2的几率是2/6，3的几率是3/6，找到这个值在原数组中的下标即可。

有了这样一个思路之后，我们看下生成后的数组[1,2,2,3,3,3]，每一位上的概率相等，所以应当是生成一个1<=x<=6的随机整数，而这个6对应的也是原数组[1,2,3]所有值之合，所以就变成了新的关系

【1】=》1，【2,3】=》2，【4,5,6】=》3

这样是不是大概就可以看出来了，此处前缀和的方式比较合适，把原来的[1,2,2,3,3,3]的数组，压缩成为[1,3,6]的数组，随机了一个1到6之间的值之后，在这个数组中找到对应的索引，就是原来数组[1,2,3]对应的索引值，返回即可。查找的这个过程一般来说用二分查找，不过看数据量，直接遍历查找也可以。