前言

按權(quán)重隨機(jī)選擇在開發(fā)中是一個相對于其他leetcode題來說比較實(shí)用，且在日常開發(fā)中會見到和使用的算法，還是有現(xiàn)實(shí)場景應(yīng)用的。所以今天leetcode每日刷題AC后，覺得還是有必要做個筆記總結(jié)下。

Leetcode 528.按權(quán)重隨機(jī)選擇

給定一個正整數(shù)數(shù)組 w ，其中 w[i] 代表下標(biāo) i 的權(quán)重（下標(biāo)從 0 開始），請寫一個函數(shù) pickIndex ，它可以隨機(jī)地獲取下標(biāo) i，選取下標(biāo) i 的概率與 w[i] 成正比。

例如，對于 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，因為數(shù)組中只有一個元素，所以唯一的選擇是返回下標(biāo) 0。

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex 將被調(diào)用不超過 10000 次

讀題：

1. w[i] 代表下標(biāo) i 的權(quán)重。

2. 選下標(biāo) i 的概率為 w[i] / sum(w)，即此權(quán)重值除以整個數(shù)組的累加和。

要求：寫個函數(shù)pickIndex，使能夠隨機(jī)獲得下標(biāo) i ，選取下標(biāo) i 的概率與 w[i] 成正比。

場景例子

比如：假如有10個游戲道具，有屠龍寶刀，也有燒火棍等等。需要隨機(jī)抽出一個發(fā)給玩家。由于道具的稀缺度，價值等不同，所以抽取的概率肯定不希望是是平均的。也就是高價值高權(quán)重獲得的概率低，低價值低權(quán)重獲得的概率高。

要實(shí)現(xiàn)這種效果，就需要給每個道具指定一個權(quán)重。比如燒火棍比較垃圾給個權(quán)重80，屠龍寶刀稀有給個權(quán)重20。即80%的概率會抽到燒火棍，這個就是基于權(quán)重的隨機(jī)算法。

本題意思相對比較簡單，與上邊的場景例子期望相反。期望對數(shù)組的元素隨機(jī)采樣，元素的權(quán)重比越高，出現(xiàn)的概率越高。

解題

以 w = [1, 2, 4, 3]為例：

sum 是10。相當(dāng)于有10個矩形格子。按照1、2、4、3來劃分4個區(qū)間。

我們在這10之內(nèi)隨機(jī)取一個數(shù)。

• 例如1，落在了第1個區(qū)間，對應(yīng)的index就是0。
• 例如2，落在了第2個區(qū)間，對應(yīng)的index就是1。
• 例如3，落在了第2個區(qū)間，對應(yīng)的index就是1。
• 例如4，落在了第3個區(qū)間，對應(yīng)的index就是2。
• 例如5，落在了第3個區(qū)間，對應(yīng)的index就是2。
• 例如6，落在了第3個區(qū)間，對應(yīng)的index就是2。
• 例如7，落在了第3個區(qū)間，對應(yīng)的index就是2。

• 例如8，落在了第4個區(qū)間，對應(yīng)的index就是3。
  .
  .

  
  
  截屏2021-08-30 上午1.48.57.png

其實(shí)說白了，原本每一個數(shù)的初始概率都為1 / 10，w 數(shù)組內(nèi)某個元素的值越大，權(quán)重越大，你期望它被選中的概率越大，那么這個值對應(yīng)的區(qū)間范圍就要越大。

所以就像 w[2] = 4，我們就讓它占據(jù)4個格子，那它占用的格子數(shù)是最多了，被選中的概率就最大了。

代碼

個人題解：

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();
    }
};

時間復(fù)雜度：

1. Solution時間復(fù)雜度為 O(n)
2. pickIndex里的lower_bound原理是二分查找，時間復(fù)雜度為 O(logn)

空間復(fù)雜度：O(n)

拓展

概率加權(quán)的隨機(jī)抽樣 (Weighted Random Sampling) – A-Res 蓄水池算法

其他算法詳細(xì)題解