前言
按權(quán)重隨機(jī)選擇在開發(fā)中是一個(gè)相對(duì)于其他leetcode題來說比較實(shí)用，且在日常開發(fā)中會(huì)見到和使用的算法橄登，還是有現(xiàn)實(shí)場(chǎng)景應(yīng)用的沐祷。所以今天leetcode每日刷題AC后脚仔，覺得還是有必要做個(gè)筆記總結(jié)下歹河。
Leetcode 528.按權(quán)重隨機(jī)選擇
給定一個(gè)正整數(shù)數(shù)組 w 齿椅，其中 w[i] 代表下標(biāo) i 的權(quán)重（下標(biāo)從 0 開始），請(qǐng)寫一個(gè)函數(shù) pickIndex 启泣，它可以隨機(jī)地獲取下標(biāo) i，選取下標(biāo) i 的概率與 w[i] 成正比示辈。
例如寥茫，對(duì)于 w = [1, 3]，挑選下標(biāo) 0 的概率為 1 / (1 + 3) = 0.25 （即矾麻，25%）纱耻，而選取下標(biāo) 1 的概率為 3 / (1 + 3) = 0.75（即，75%）险耀。
也就是說弄喘，選取下標(biāo) i 的概率為 w[i] / sum(w) 。
示例 1：
輸入：
["Solution","pickIndex"]
[[[1]],[]]輸出：
[null,0]解釋：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0甩牺，因?yàn)閿?shù)組中只有一個(gè)元素蘑志，所以唯一的選擇是返回下標(biāo) 0。
1 <= w.length <= 100001 <= w[i] <= 10^5pickIndex將被調(diào)用不超過10000次
讀題：
w[i] 代表下標(biāo) i 的權(quán)重贬派。
選下標(biāo) i 的概率為 w[i] / sum(w)急但，即此權(quán)重值除以整個(gè)數(shù)組的累加和。
要求：寫個(gè)函數(shù)pickIndex搞乏，使能夠隨機(jī)獲得下標(biāo) i 波桩，選取下標(biāo) i 的概率與 w[i] 成正比。
場(chǎng)景例子
比如：假如有10個(gè)游戲道具请敦，有屠龍寶刀镐躲，也有燒火棍等等。需要隨機(jī)抽出一個(gè)發(fā)給玩家侍筛。由于道具的稀缺度萤皂，價(jià)值等不同，所以抽取的概率肯定不希望是是平均的勾笆。也就是高價(jià)值高權(quán)重獲得的概率低敌蚜，低價(jià)值低權(quán)重獲得的概率高。
要實(shí)現(xiàn)這種效果窝爪，就需要給每個(gè)道具指定一個(gè)權(quán)重弛车。比如燒火棍比較垃圾給個(gè)權(quán)重80齐媒，屠龍寶刀稀有給個(gè)權(quán)重20。即80%的概率會(huì)抽到燒火棍纷跛，這個(gè)就是基于權(quán)重的隨機(jī)算法喻括。
本題意思相對(duì)比較簡(jiǎn)單，與上邊的場(chǎng)景例子期望相反贫奠。期望對(duì)數(shù)組的元素隨機(jī)采樣唬血，元素的權(quán)重比越高，出現(xiàn)的概率越高唤崭。
解題
以 w = [1, 2, 4, 3]為例：
sum 是10拷恨。相當(dāng)于有10個(gè)矩形格子。按照1谢肾、2腕侄、4、3來劃分4個(gè)區(qū)間芦疏。
我們?cè)谶@10之內(nèi)隨機(jī)取一個(gè)數(shù)冕杠。
- 例如1，落在了第1個(gè)區(qū)間酸茴，對(duì)應(yīng)的index就是0分预。
- 例如2，落在了第2個(gè)區(qū)間薪捍，對(duì)應(yīng)的index就是1笼痹。
- 例如3，落在了第2個(gè)區(qū)間酪穿，對(duì)應(yīng)的index就是1与倡。
- 例如4，落在了第3個(gè)區(qū)間昆稿，對(duì)應(yīng)的index就是2纺座。
- 例如5，落在了第3個(gè)區(qū)間溉潭，對(duì)應(yīng)的index就是2净响。
- 例如6，落在了第3個(gè)區(qū)間喳瓣，對(duì)應(yīng)的index就是2馋贤。
- 例如7，落在了第3個(gè)區(qū)間畏陕，對(duì)應(yīng)的index就是2配乓。
-
例如8，落在了第4個(gè)區(qū)間，對(duì)應(yīng)的index就是3犹芹。
.
.
截屏2021-08-30 上午1.48.57.png
其實(shí)說白了崎页，原本每一個(gè)數(shù)的初始概率都為1 / 10，w 數(shù)組內(nèi)某個(gè)元素的值越大腰埂，權(quán)重越大飒焦，你期望它被選中的概率越大，那么這個(gè)值對(duì)應(yīng)的區(qū)間范圍就要越大屿笼。
所以就像 w[2] = 4牺荠，我們就讓它占據(jù)4個(gè)格子，那它占用的格子數(shù)是最多了驴一，被選中的概率就最大了休雌。
代碼
個(gè)人題解：
class Solution {
public:
Solution(vector<int>& w) {
preSum = w;
int size = w.size();
for (int i = 1; i < size; i++) {
preSum[i] += preSum[i - 1];
}
}
int pickIndex() {
int p = rand() % preSum.back() + 1;
return lower_bound(preSum.begin(), preSum.end(), p) - preSum.begin();
}
private:
vector<int> preSum;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(w);
* int param_1 = obj->pickIndex();
*/
官方題解：
class Solution {
private:
mt19937 gen;
uniform_int_distribution<int> dis;
vector<int> pre;
public:
Solution(vector<int>& w): gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0)) {
partial_sum(w.begin(), w.end(), back_inserter(pre));
}
int pickIndex() {
int x = dis(gen);
return lower_bound(pre.begin(), pre.end(), x) - pre.begin();
}
};
時(shí)間復(fù)雜度：
- Solution時(shí)間復(fù)雜度為 O(n)
- pickIndex里的lower_bound原理是二分查找，時(shí)間復(fù)雜度為 O(logn)
空間復(fù)雜度：O(n)
拓展
概率加權(quán)的隨機(jī)抽樣 (Weighted Random Sampling) – A-Res 蓄水池算法
