27. Leetcode 528. Random Pick with Weight.md

528. Random Pick with Weight

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

For example, given an input list of values w = [2, 8], when we pick up a number out of it, the chance is that 8 times out of 10 we should pick the number 1 as the answer since it's the second element of the array (w[1] = 8).

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

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. Since there is only one single element on the array the only option is to return the first element.

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

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It's returning the second element (index = 1) that has probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It's returning the first element (index = 0) that has probability of 1/4.

Since this is a randomization problem, multiple answers are allowed so the following outputs can be considered correct :
[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]
......
and so on.
 

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

---

Solutions

---

Method2: Sampling + Binary Search

/*
Method1: Sampling + Binary Search
given an array of integer A
1. calculate prefix sum: prefixSum(A)
2. randomly generate a percentage: p
3. multiply P with the sum(A) to get B
4. Binary Search to see where B will fall: if(A[i] > B), then return i

//T(n) = O(nlgn)
*/

class Solution {
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for(int i = 0; i < w.size(); i++){
            sum += w[i];
            prefixSum.push_back(sum);
        }
        srand(time(NULL));
    }
    
    int pickIndex() {
        double percent = static_cast<double>(rand()) / RAND_MAX;
        double target = percent*prefixSum.back();
        //binary search
        //Note: we need to first i s.t. prefixSum[i] > target, by scanning from left to right
        int i = 0, j = prefixSum.size()-1;
        /*
        note: while(i<=j) may cause time limit exceeded
        bc j = mid, not j = mid-1
        */
        while(i < j){
            int mid = (i+j)/2;
            if(prefixSum[mid] >= target){
                j = mid;
            }else{
                i = mid+1;
            }
        }
        return i;
    }
private:
    vector<int> prefixSum;
};

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

---

Method1: Sampling + Linary Search

/*
Method1: Sampling
given an array of integer A
1. calculate prefix sum: prefixSum(A)
2. randomly generate a percentage: p
3. multiply P with the sum(A) to get B
4. scan from left to right to see where B will fall: if(A[i] > B), then return i
//T(n) = O(n)
*/

class Solution {
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for(int i = 0; i < w.size(); i++){
            sum += w[i];
            prefixSum.push_back(sum);
        }
        srand(time(NULL));
    }
    
    int pickIndex() {
        double percent = static_cast<double>(rand()) / RAND_MAX;
        double target = percent*prefixSum.back();
        for(int i = 0; i < prefixSum.size(); i++){
            if(target < prefixSum[i]){
                return i;
            }
        }
        //the last statement will never be executed
        return prefixSum.size()-1;
    }
private:
    vector<int> prefixSum;
};

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