528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight/
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.
Intuition
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| int[] weights; | |
| int[] prefixes; | |
| Random random; | |
| public Solution(int[] w) { | |
| weights = w; | |
| prefixes = new int[w.length]; | |
| prefixes[0] = w[0]; | |
| for (int i = 1; i < w.length; i++) { | |
| prefixes[i] = w[i] + prefixes[i - 1]; | |
| } | |
| random = new Random(); | |
| } | |
| public int pickIndex() { | |
| int target = random.nextInt(prefixes[prefixes.length - 1]) + 1; | |
| int lo = 0, hi = prefixes.length - 1; | |
| int ans = lo; | |
| while (lo <= hi) { | |
| int mid = lo + (hi - lo) / 2; | |
| if (target <= prefixes[mid]) { | |
| ans = mid; | |
| hi = mid - 1; | |
| } else { | |
| lo = mid + 1; | |
| } | |
| } | |
| return ans; | |
| } | |
| } | |
| /** | |
| * Your Solution object will be instantiated and called as such: | |
| * Solution obj = new Solution(w); | |
| * int param_1 = obj.pickIndex(); | |
| */ |
