June Leetcoding Challenge(6.5)

Random Pick with Weight

Solution

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]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,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.

思路：

代码：

class Solution {
    int[] tmp;
    Random rand;
    public Solution(int[] w) {
        this.tmp = w.clone();
        this.rand = new Random();
        for(int i=1;i<w.length;i++)
            tmp[i] +=tmp[i-1];
    }
    
    public int pickIndex() {
        int x = rand.nextInt(tmp[tmp.length-1])+1;
        int index = Arrays.binarySearch(tmp,x);
        if(index<0)
            index = -(index+1);
        return index;
    }
}

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