528. Random Pick with Weight Medium

1/**
2 * [528] Random Pick with Weight
3 *
4 * You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i^th index.
5 * You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
6 * 
7 * 	For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
8 * 
9 *  
10 * Example 1:
11 * 
12 * Input
13 * ["Solution","pickIndex"]
14 * [[[1]],[]]
15 * Output
16 * [null,0]
17 * Explanation
18 * Solution solution = new Solution([1]);
19 * solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
20 * 
21 * Example 2:
22 * 
23 * Input
24 * ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
25 * [[[1,3]],[],[],[],[],[]]
26 * Output
27 * [null,1,1,1,1,0]
28 * Explanation
29 * Solution solution = new Solution([1, 3]);
30 * solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
31 * solution.pickIndex(); // return 1
32 * solution.pickIndex(); // return 1
33 * solution.pickIndex(); // return 1
34 * solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
35 * Since this is a randomization problem, multiple answers are allowed.
36 * All of the following outputs can be considered correct:
37 * [null,1,1,1,1,0]
38 * [null,1,1,1,1,1]
39 * [null,1,1,1,0,0]
40 * [null,1,1,1,0,1]
41 * [null,1,0,1,0,0]
42 * ......
43 * and so on.
44 * 
45 *  
46 * Constraints:
47 * 
48 * 	1 <= w.length <= 10^4
49 * 	1 <= w[i] <= 10^5
50 * 	pickIndex will be called at most 10^4 times.
51 * 
52 */
53pub struct Solution {}
54
55// problem: https://leetcode.com/problems/random-pick-with-weight/
56// discuss: https://leetcode.com/problems/random-pick-with-weight/discuss/?currentPage=1&orderBy=most_votes&query=
57
58// submission codes start here
59
60struct Solution {
61        vec![]
62    }
63
64
65/** 
66 * `&self` means the method takes an immutable reference.
67 * If you need a mutable reference, change it to `&mut self` instead.
68 */
69impl Solution {
70
71    fn new(w: Vec<i32>) -> Self {
72        
73    }
74    
75    fn pick_index(&self) -> i32 {
76        
77    }
78}
79
80/**
81 * Your Solution object will be instantiated and called as such:
82 * let obj = Solution::new(w);
83 * let ret_1: i32 = obj.pick_index();
84 */
85
86// submission codes end
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_528() {
94    }
95}
96