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
This C implementation uses binary search to efficiently find the index corresponding to the random target. After setting up the cumulative sum array, a target number is generated, and binary search is used to pinpoint the index.