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.
Python'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#include <stdio.h>
2#include <stdlib.h>
3
4int compareInts(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8typedef struct {
9 int* prefixSum;
10 int n;
11} Solution;
12
13Solution* solutionCreate(int* w, int wSize) {
14 Solution* obj = (Solution*)malloc(sizeof(Solution));
15 obj->prefixSum = (int*)malloc(sizeof(int) * wSize);
16 obj->n = wSize;
17 obj->prefixSum[0] = w[0];
18 for (int i = 1; i < wSize; ++i) {
19 obj->prefixSum[i] = obj->prefixSum[i - 1] + w[i];
20 }
21 return obj;
22}
23
24int solutionPickIndex(Solution* obj) {
25 int totalWeight = obj->prefixSum[obj->n - 1];
26 int target = rand() % totalWeight;
27 int left = 0, right = obj->n - 1;
28 while (left < right) {
29 int mid = left + (right - left) / 2;
30 if (obj->prefixSum[mid] <= target) {
31 left = mid + 1;
32 } else {
33 right = mid;
34 }
35 }
36 return left;
37}
38
39void solutionFree(Solution* obj) {
40 free(obj->prefixSum);
41 free(obj);
42}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.