Leetcode Problem 528. Random Pick with Weight
Leetcode Solutions
Prefix Sums with Binary Search
- Calculate the prefix sum array from the input weights.
- Store the total sum of weights for scaling the random number.
- When
pickIndex()is called, generate a random number between 0 and 1, then scale it by the total sum to get the target offset. - Perform a binary search on the prefix sum array to find the first prefix sum that is larger than the target offset.
- Return the index of this prefix sum as the result of
pickIndex().
Prefix Sums with Linear Search
Ask Question
Programming Language
Purpose:
image/screenshot of info(optional)
Full Screen
Loading...
Suggested Answer
Answer
Full Screen
Copy Answer Code
Loading...
OR