难度 中等

题目 Leetcode:

You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed).

We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).

More formally, the probability of picking index i is w[i] / sum(w).

题目解析

前缀和然后二分查找，理解了还是比较容易接受的，具体的题解明天补一下吧，今天在考完科四太兴奋了，出去嗨了一天，有点太累了，希望人没事

 1 class Solution {
 2 public:
 3     vector<int> a;
 4     int sum = 0;
 5     Solution(vector<int>& w) {
 6         for(int i = 0;i<w.size();i++)
 7         {
 8             sum+=w[i];//前缀和
 9             a.push_back(sum-1);
10         }
11     }
12     int pickIndex() {
13         int t = rand() % sum;
14         return lower_bound(a.begin(),a.end(),t)-a.begin();
15     }
16 };

2021-8-30 Random Pick with Weight