Sponsored
Sponsored
This approach involves creating a cumulative sum array based on the provided weights. The idea is to convert the weight array into a cumulative distribution, where each element represents the summed result of all previous weights including the current one. When we generate a random number, we search for its position in this cumulative array to determine which index to return.
Time Complexity: O(N) for initialization, O(N) for the pickIndex.
Space Complexity: O(N) due to the cumulative sum storage.
1class Solution {
2 constructor(w) {
3 this.prefixSum = [];
4 let sum = 0;
5 for (const weight of w) {
6 sum += weight;
7 this.prefixSum.push(sum);
8 }
9 }
10 pickIndex() {
11 const totalWeight = this.prefixSum[this.prefixSum.length - 1];
12 const target = Math.floor(Math.random() * totalWeight);
13 for (let i = 0; i < this.prefixSum.length; i++) {
14 if (target < this.prefixSum[i]) {
15 return i;
16 }
17 }
18 }
19}JavaScript uses its Math library to generate a random number, and the cumulative distribution is mapped using an array which is linearly searched to find the corresponding index to return.
This optimized approach also uses a cumulative sum array, but instead of performing a linear search to find the appropriate index, we use a binary search. This greatly improves the efficiency when determining which index corresponds to a given cumulative value, especially beneficial for larger arrays.
Time Complexity: O(N) for initialization, O(log N) for pickIndex.
Space Complexity: O(N) for the cumulative sum array.
1
The Python solution uses the 'bisect' module to implement a binary search, specifically 'bisect_left', allowing quick location of the correct index to return for a given cumulative target.