Algorithm
Problem Name: 528. Random Pick with Weight
Problem Link: https://leetcode.com/problems/random-pick-with-weight/
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
- For example, if
w = [1, 3], the probability of picking index0is1 / (1 + 3) = 0.25(i.e.,25%), and the probability of picking index1is3 / (1 + 3) = 0.75(i.e.,75%).
Example 1:
Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0] Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0] Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4. Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.
Constraints:
1 <= w.length <= 1041 <= w[i] <= 105pickIndexwill be called at most104times.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
private int[] prefixSum;
private int totalPrefixSum;
public Solution(int[] w) {
this.prefixSum = new int[w.length];
int currPrefixSum = 0;
for (int i = 0; i < w.length; i++) {
currPrefixSum += w[i];
this.prefixSum[i] = currPrefixSum;
}
this.totalPrefixSum = currPrefixSum;
}
public int pickIndex() {
double randomTarget = this.totalPrefixSum * Math.random();
int left = 0;
int right = this.prefixSum.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (randomTarget > this.prefixSum[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const Solution = function(w) {
this.a = []
let sum = 0
for (let i = 0, len = w.length; i < len; i++) {
sum += w[i]
this.a[i] = sum
}
}
Solution.prototype.pickIndex = function() {
const len = this.a.length
const sum = this.a[len - 1]
const rand = ((Math.random() * sum) >> 0) + 1
let l = 0,
h = len - 1
while (l < h) {
const mid = (l + h) >> 1
if (this.a[mid] === rand) return mid
else if (this.a[mid] < rand) l = mid + 1
else h = mid
}
return l
}
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def __init__(self, w):
self.ranges, sm = [], 0
for weight in w:
self.ranges.append([sm, sm + weight])
sm += weight
self.mn, self.mx = 1, sm
def pickIndex(self):
num, l, r = random.randint(self.mn, self.mx), 0, len(self.ranges) - 1
while l <= r:
mid = (l + r) // 2
if self.ranges[mid][1] < num:
l = mid + 1
elif num <= self.ranges[mid][0]:
r = mid - 1
else:
return mid
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0528_RandomPickWithWeight
{
private readonly int[] prefixSums;
private readonly int totalSum;
private readonly Random random;
public _0528_RandomPickWithWeight(int[] w)
{
prefixSums = new int[w.Length];
for (int i = 0; i < w.Length; i++)
{
totalSum += w[i];
prefixSums[i] = totalSum;
}
random = new Random();
}
public int PickIndex()
{
var target = random.Next(totalSum) + 1;
int lo = 0, hi = prefixSums.Length - 1;
while (lo < = hi)
{
int mid = lo + (hi - lo) / 2;
if (target == prefixSums[mid]) return mid;
if (target > prefixSums[mid])
lo = mid + 1;
else
hi = mid - 1;
}
return lo;
}
}
}
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]