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 #1
pickIndex O(n) time
class Solution { private double calls; private int[] count; private double totalWeight; private Random rand; private int[] w; public Solution(int[] w) { count = new int[w.length]; calls = 0; rand = new Random(); this.w = w; for (int i : w) totalWeight += (double)i; } public int pickIndex() { calls++; int next = rand.nextInt(w.length); while (count[next] / calls > w[next] / totalWeight) { next = rand.nextInt(w.length); } count[next]++; return next; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(w); * int param_1 = obj.pickIndex(); */
Solution #2
与Solution #1用array的大小当做random范围不同,这里我们用整个array的totalWeight当做random的范围,然后用accumulative sum来划分原来的weight array。然后用二分法找到落入该区间的所属的index
O(lgN)
class Solution { private int[] sums; private Random rand = new Random(); private int range; private int n; public Solution(int[] w) { n = w.length; sums = new int[n]; sums[0] = w[0] - 1; for (int i = 1; i < n; i++) { sums[i] = sums[i - 1] + w[i]; } range = sums[n - 1]; } public int pickIndex() { int target = rand.nextInt(range + 1); int left = 0, right = n - 1; while (left < right) { int mid = (left + right) / 2; if (sums[mid] == target) { return mid; }else if (sums[mid] > target) { right = mid; }else { left = mid + 1; } } return left; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(w); * int param_1 = obj.pickIndex(); */
No comments:
Post a Comment