[LeetCode] 528. Random Pick with Weight

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1. 1 <= w.length <= 10000
2. 1 <= w[i] <= 10^5
3. pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren‘t any.

按权重随机选择。题意是给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

注意这个题最后返回的是权重w里面的index。我直接用例子讲思路了。举个例子，比如权重w = [2, 5, 3, 4], 那么权重和wsum = [2, 7, 10, 14]，对于w中的每一个元素，被抽中的几率分别是[2/14, 5/14, 3/14, 4/14]

因为整个input的权重和是14，所以取random数字可以在[1, 14]这个范围内取，然后可以把这14个数字按照权重分配给w的下标，结果如下

idx in [1,2] return 0
idx in [3,7] return 1
idx in [8,10] return 2
idx in [11,14] return 3

当得到这个随机数之后，就去权重和里面找，比如如果随机数是4，在wsum = [2, 7, 10, 14]范围内做二分，最后会返回下标1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     Random random;
 3     int[] wSums;
 4 
 5     public Solution(int[] w) {
 6         this.random = new Random();
 7         for (int i = 1; i < w.length; i++) {
 8             w[i] += w[i - 1];
 9         }
10         this.wSums = w;
11     }
12 
13     public int pickIndex() {
14         int len = wSums.length;
15         int idx = random.nextInt(wSums[len - 1]) + 1;
16         int left = 0, right = len - 1;
17         // search position 
18         while (left < right) {
19             int mid = left + (right - left) / 2;
20             if (wSums[mid] == idx) {
21                 return mid;
22             } else if (wSums[mid] < idx) {
23                 left = mid + 1;
24             } else {
25                 right = mid;
26             }
27         }
28         return left;
29     }
30 }
31 
32 /**
33  * Your Solution object will be instantiated and called as such:
34  * Solution obj = new Solution(w);
35  * int param_1 = obj.pickIndex();
36  */

LeetCode 题目总结

[LeetCode] 528. Random Pick with Weight

原文：https://www.cnblogs.com/cnoodle/p/13054334.html