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 random
2
3class Solution:
4
5 def __init__(self, w):
6 self.prefixSum = []
7 current_sum = 0
8 for weight in w:
9 current_sum += weight
10 self.prefixSum.append(current_sum)
11
12 def pickIndex(self):
13 target = random.randint(0, self.prefixSum[-1] - 1)
14 for i, total in enumerate(self.prefixSum):
15 if target < total:
16 return iPython's 'random' module is utilized to generate a random number. The cumulative weight distribution is maintained in a list, and we go through it linearly to find the appropriate index.
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
public class Solution {
private int[] prefixSum;
private Random random;
public Solution(int[] w) {
prefixSum = new int[w.Length];
prefixSum[0] = w[0];
for (int i = 1; i < w.Length; i++) {
prefixSum[i] = prefixSum[i - 1] + w[i];
}
random = new Random();
}
public int PickIndex() {
int target = random.Next(prefixSum[prefixSum.Length - 1]);
int left = 0, right = prefixSum.Length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (prefixSum[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}
}This C# implementation manually performs binary search to find the index with fewer comparisons, increasing efficiency in target determination.