# 0528. Random Pick with Weight
###### tags: `Leetcode` `Medium` `FaceBook` `Binary Search` `Prefix Sum`
Link: https://leetcode.com/problems/random-pick-with-weight/
## 思路
PrefixSum + BinarySearch
## Code

class Solution {
    int[] pre;
    int total;
    Random rand = new Random();
    public Solution(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for(int i = 1;i < w.length;i++){
            pre[i] = pre[i-1]+w[i];
        }
        total = pre[w.length-1];
    }
    
    public int pickIndex() {
        int selected = rand.nextInt(total);
        return binarySearch(selected);
    }
    
    public int binarySearch(int selected){
        int begin = 0;
        int end = pre.length-1;
        while(begin<end){
            int mid = begin+(end-begin)/2;
            if(pre[mid]<=selected){
                begin = mid+1;
            }
            else if(pre[mid]>selected){
                end = mid;
            }
            
        }
        return begin;
    }
}

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

## Result
Runtime: 21 ms, faster than **92.36%** of Java online submissions for Random Pick with Weight.
Memory Usage: 44.2 MB, less than **46.41%** of Java online submissions for Random Pick with Weight.