?LeetCode刷題實(shí)戰(zhàn)528：按權(quán)重隨機(jī)選擇
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
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).
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%).
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例 1：
輸入：
["Solution","pickIndex"]
[[[1]],[]]
輸出：
[null,0]
解釋?zhuān)?br mpa-from-tpl="t">Solution solution = new?Solution([1]);
solution.pickIndex(); // 返回 0，因?yàn)閿?shù)組中只有一個(gè)元素，所以唯一的選擇是返回下標(biāo) 0。
示例 2：
輸入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
輸出：
[null,1,1,1,1,0]
解釋?zhuān)?br mpa-from-tpl="t">Solution solution = new?Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下標(biāo) 1，返回該下標(biāo)概率為 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下標(biāo) 0，返回該下標(biāo)概率為 1/4 。
由于這是一個(gè)隨機(jī)問(wèn)題，允許多個(gè)答案，因此下列輸出都可以被認(rèn)為是正確的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
諸若此類(lèi)。
解題
class?Solution?{
public:
????vector<int> preSum;
????int?n;
????Solution(vector<int>& w) {
????????n = w.size();
????????preSum.resize(n + 1, 0);
????????for(int?i = 1; i <= n; ++i) {
????????????preSum[i] = preSum[i - 1] + w[i - 1];
????????}
????}
????
????int?pickIndex()?{
????????int?oneRandNum = rand() % preSum[n] + 1; // 取一個(gè)隨機(jī)數(shù)，+1是為了將隨機(jī)數(shù)映射到范圍[1, 2, ... preSum[n]]內(nèi)
????????return?lower_bound(preSum.begin() + 1, preSum.end(), oneRandNum) - preSum.begin() - 1; // 找到第一個(gè)大于等于oneRandNum的前綴和在原數(shù)組中對(duì)應(yīng)的下標(biāo)，就是答案
????}
};