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.
1import java.util.*;
2
3class Solution {
4 private int[] prefixSum;
5 private Random random;
6
7 public Solution(int[] w) {
8 prefixSum = new int[w.length];
9 prefixSum[0] = w[0];
10 for (int i = 1; i < w.length; i++) {
11 prefixSum[i] = prefixSum[i - 1] + w[i];
12 }
13 random = new Random();
14 }
15
16 public int pickIndex() {
17 int totalWeight = prefixSum[prefixSum.length - 1];
18 int target = random.nextInt(totalWeight);
19 for (int i = 0; i < prefixSum.length; i++) {
20 if (target < prefixSum[i]) {
21 return i;
22 }
23 }
24 return -1; // Should never be reached
25 }
26}In Java, a Random instance is used to generate random numbers. The cumulative distribution is stored in an array and checked linearly. Java array handling is directly used for initialization and computation.
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.