528. Random Pick with Weight

---

My Solution

The Key Idea for Solving This Coding Question

Example:

$w=[1,3]$ =>

$data=[1,4]$
Therefore,

$x$ can be

$0$,

$1$,

$2$ or

$3$.
We map

$x=0$ to

$data[0]$ which is

$1$.

$x=1,2,3$ to

$data[1]$ which is

$4$.
Therefore, we should find a value in

$data$ that is greater than

$x$.

C++ Code

class Solution {
public:
    Solution(vector<int> &w) {
        prefixSum.resize(w.size());
        prefixSum[0] = w[0];
        for (int i = 1; i < prefixSum.size(); ++i) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
    }

    int pickIndex() {
        int x = rand() % prefixSum.back();

        // Use binary search to find a prefix sum (prefixSum[middle])
        // that is greater than x.
        int left = 0, right = prefixSum.size() - 1;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (prefixSum[middle] <= x) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        if (prefixSum[left] <= x) {
            ++left;
        }

        return left;
    }

private:
    vector<int> prefixSum;
};

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

Time Complexity

• Sloution
  
  $O(1)$
• pickIndex
  
  $O(logn)$
  
  $n$ is the length of w.

Space Complexity

• Sloution
  
  $O(n)$
• pickIndex
  
  $O(1)$

Miscellane