> For the complete documentation index, see [llms.txt](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/search/cha-zhao/random-pick-with-weight.md).

# Random Pick with Weight

medium 原题链接：https\://leetcode.com/problems/random-pick-with-weight/

## Random Pick with Weight

原题链接：<https://leetcode.com/problems/random-pick-with-weight/>

### 描述

> 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)`.

### 例子

> Input ：
>
> \["Solution","pickIndex"]&#x20;
>
> \[\[\[1]],\[]]&#x20;
>
> Output ：
>
> \[null,0]
>
> Explanation ：
>
> Solution solution = new Solution(\[1]);&#x20;
>
> solution.pickIndex();&#x20;
>
> // return 0. Since there is only one single element on the array the only option is to return the first element.

### 题意解释

the array of {1, 3, 4, 6}&#x20;

the pickIndex() call will have&#x20;

1/(1+3+4+6) = 1/14 = \~7% chance of picking index 0;&#x20;

3/14 = 21% change of picking index 1;

4/14 = 29% change of picking index 2;&#x20;

and 6/14 = 43% of picking index 3.

### 解法一

binary search

```
class Solution {
    public:
    vector<int> s;
    Solution(vector<int>& w) {
        for (int ind : w){
            if(s.empty())
                s.push_back(ind);
            else
                s.push_back(ind + s.back());
        }
    }
    
    int pickIndex() {
        int x = s.back();
        int index = rand() % x;
        auto it = upper_bound(s.begin(), s.end(),index);
        return it - s.begin();
    }
};
```

## 总结