Question

Formatted question description: https://leetcode.ca/all/528.html




Algorithm

This question gives an array of weights.

Let us randomly pick points based on the weights. The current points are not randomly selected with equal probability, but should be selected based on different weights. For example, in example 2, the weight is [1, 3], which means that there are two points, the weights are 1 and 3 respectively, then the probability of one point is one-fourth, and the probability of the other one is four-quarters. three.

Since our rand() function is random with equal probability, then how can we weight random, we can use a trick, since the weights are 1 and 3, the sum is 4, then we now assume that there are 4 points, Then randomly pick a point with equal probability.

After random to the first point, it represents the original first point, and random to the last three points represents the original second point, so that the weight is random. Then we can create the cumulative sum array of the weight array.

For example, if the weight array is [1, 3, 2], then the cumulative sum array is [1, 4, 6], and the entire weight sum is 6, we rand() % 6, you can randomly get a number in the range [0, 5], random to 0 is the first point, random to 1, 2, 3 is the second point, random to 4, 5 is the third Point, so we randomly find a number x, and then add and find the first number greater than the random number x in the array, and use the binary search method to find the coordinates of the first number greater than the random number x, which is what you want

Code

Java

• public class Random_Pick_with_Weight {

// i hate these stats random questions
class Solution {
private int[] presum;
private int n;
private Random rand;

public Solution(int[] w) {
n = w.length;
presum = new int[n];
rand = new Random();
presum[0] = w[0];
for (int i = 1; i < n; i++) presum[i] = presum[i - 1] + w[i];
}

public int pickIndex() {
int r = rand.nextInt(presum[n - 1]) + 1;
int i = Arrays.binarySearch(presum, r);
if (i < 0) i = -(i + 1);
return i;
}
}

}


• // OJ: https://leetcode.com/problems/random-pick-with-weight/
// Time: O(W) for both APIs
// Space: O(W)
class Solution {
private:
int sum;
vector<int> w;
public:
Solution(vector<int> w): w(w) {
srand (time(NULL));
sum = accumulate(w.begin(), w.end(), 0);
}

int pickIndex() {
int r = rand() % sum;
for (int i = 0; i < w.size(); ++i) {
r -= w[i];
if (r < 0) return i;
}
}
};

• class Solution:

def __init__(self, w):
"""
:type w: List[int]
"""
self.preSum = [0] * len(w)
self.preSum[0] = w[0]
for i in range(1, len(w)):
self.preSum[i] = self.preSum[i - 1] + w[i]

def pickIndex(self):
"""
:rtype: int
"""
total = self.preSum[-1]
rand = random.randint(0, total - 1)
left, right = 0, len(self.preSum) - 1
while left + 1 < right:
mid = (left + right) // 2
if rand >= self.preSum[mid]:
left = mid
else:
right = mid
if rand < self.preSum[left]:
return left
return right

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()


Java

• java class Solution { int[] accumulatedWeights; int totalWeight;

public Solution(int[] w) {
int length = w.length;
accumulatedWeights = new int[length];
accumulatedWeights[0] = w[0];
for (int i = 1; i < length; i++)
accumulatedWeights[i] = accumulatedWeights[i - 1] + w[i];
totalWeight = accumulatedWeights[length - 1];
}

public int pickIndex() {
int random = (int) (Math.random() * totalWeight);
int index = binarySearch(random);
return index;
}

private int binarySearch(int target) {
int low = 0, high = accumulatedWeights.length;
while (low < high) {
int mid = (high - low) / 2 + low;
int curWeight = accumulatedWeights[mid];
if (curWeight == target)
return mid + 1;
else if (curWeight > target)
high = mid;
else
low = mid + 1;
}
return low;
} }


/**

• Your Solution object will be instantiated and called as such:
• Solution obj = new Solution(w);
• int param_1 = obj.pickIndex(); */
• // OJ: https://leetcode.com/problems/random-pick-with-weight/
// Time: O(W) for both APIs
// Space: O(W)
class Solution {
private:
int sum;
vector<int> w;
public:
Solution(vector<int> w): w(w) {
srand (time(NULL));
sum = accumulate(w.begin(), w.end(), 0);
}

int pickIndex() {
int r = rand() % sum;
for (int i = 0; i < w.size(); ++i) {
r -= w[i];
if (r < 0) return i;
}
}
};

• class Solution:

def __init__(self, w):
"""
:type w: List[int]
"""
self.preSum = [0] * len(w)
self.preSum[0] = w[0]
for i in range(1, len(w)):
self.preSum[i] = self.preSum[i - 1] + w[i]

def pickIndex(self):
"""
:rtype: int
"""
total = self.preSum[-1]
rand = random.randint(0, total - 1)
left, right = 0, len(self.preSum) - 1
while left + 1 < right:
mid = (left + right) // 2
if rand >= self.preSum[mid]:
left = mid
else:
right = mid
if rand < self.preSum[left]:
return left
return right

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()