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.
1using System;
2
3public class Solution {
4 private int[] prefixSum;
5 private Random rand;
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 rand = new Random();
14 }
15
16 public int PickIndex() {
17 int totalWeight = prefixSum[prefixSum.Length - 1];
18 int target = rand.Next(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 happen
25 }
26}C# leverages the 'Random' class for generating random numbers. The cumulative sum array is traversed linearly to select an index based on the generated random number.
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.