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#include <cstdlib>
#include <algorithm>
using namespace std;
class Solution {
vector<int> prefixSum;
public:
Solution(vector<int>& w) {
int sum = 0;
for (int weight : w) {
sum += weight;
prefixSum.push_back(sum);
}
}
int pickIndex() {
int totalWeight = prefixSum.back();
int target = rand() % totalWeight;
return lower_bound(prefixSum.begin(), prefixSum.end(), target + 1) - prefixSum.begin();
}
};This C++ solution employs the standard library's 'lower_bound' function, which performs a binary search to identify the first element not less than the target, giving the desired index efficiently.