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.
1typedef struct {
2 int* prefixSum;
3 int n;
4} Solution;
5
6Solution* solutionCreate(int* w, int wSize) {
7 Solution* obj = (Solution*)malloc(sizeof(Solution));
8 obj->prefixSum = (int*)malloc(sizeof(int) * wSize);
9 obj->n = wSize;
10 obj->prefixSum[0] = w[0];
11 for (int i = 1; i < wSize; ++i) {
12 obj->prefixSum[i] = obj->prefixSum[i - 1] + w[i];
13 }
14 return obj;
15}
16
17int solutionPickIndex(Solution* obj) {
18 int totalWeight = obj->prefixSum[obj->n - 1];
19 int target = rand() % totalWeight;
20 for (int i = 0; i < obj->n; i++) {
21 if (target < obj->prefixSum[i]) {
22 return i;
23 }
24 }
25 return -1; // Should never reach here
26}
27
28void solutionFree(Solution* obj) {
29 free(obj->prefixSum);
30 free(obj);
31}This C solution implements a cumulative sum array ('prefixSum') to store the cumulative weights of the input array 'w'. The 'solutionPickIndex' function then generates a random number within the range of the total sum of weights and searches for the corresponding index in the cumulative sum array. The search is done linearly here.
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.