随机权值选择算法

Posted on Edited on Views:

按权值随机选择算法

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入：
["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]
......
诸若此类。

来源：力扣（LeetCode）

方案一：前缀和+二分查找

把待选择的数放平到线段上

如:

待选择的数组：[ 1,3,2,4,2 ]

按数字权值大小在线段上分布放平:

1___3__2____4__2

求出前缀和:

1___4__6____10__12

不难发现：现在前缀和数组可以表示，每一个数字占所有可能选择的几率（线段长度除以总长度）

那如果选择的是7呢？

这时，比如数组左边抛出一个小球，随机落到7点处，即6-10之间，其实已经是10的概率分布范围了。这时需要二分查找，查找当前数字的最左值，即10的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {

    int nums[];//前缀和数组

    public Solution(int[] w) {
        int n = w.length;
        nums = new int[n + 1];
        //第0位为占位符，可以理解为小球抛出点
        for (int i = 1; i <= n; i++) nums[i] = nums[i - 1] + w[i - 1];
    }

    public int pickIndex() {
        int n = nums.length;
        int t = (int) (Math.random() * nums[n - 1]) + 1;
        //二分法，获取最左边界值
        int l = 1;
        int r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] < t) l = mid;
            else r = mid - 1;
        }
        return nums[r] < t ? r : r - 1;
    }
}