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 <= 100001 <= w[i] <= 10^5pickIndexwill be called at most10000times.
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_; }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment