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 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex
will be called at most10000
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.
Solution: Binary Search
Crate a cumulative weight array, random sample a “weight”, do a binary search to see which bucket that weight falls in.
e.g. w = [2, 3, 1, 4], sum = [2, 5, 6, 10]
sample 3 => index = 1
sample 7 => index = 3
Time complexity: Init: O(n) Pick: O(logn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: Solution(vector<int> w): sums_(std::move(w)) { partial_sum(begin(sums_), end(sums_), begin(sums_)); } int pickIndex() { int s = rand() % sums_.back(); return upper_bound(begin(sums_), end(sums_), s) - begin(sums_); } private: vector<int> sums_; }; |