Leetcode題解 Python & C#：六月挑戰DAY5 Random Pick with Weight

給一串正整數權重 w ，w[i] 代表 i 的權重。然後要寫一個 pickIndex 方法，以加權的機率抽出一個 i 。

雖然說 Python 的 random 模組有方法可以模擬做加權抽樣，但是速度不夠快，以致於超時，所以要減少 random 的使用，靠自己寫更有效率的代碼。

(這也是很少見的專門模組效率會遜於自撰的)

加權抽樣若以 1 為單位，把所有 index 放入一個假想的箱子，權重為 1 放1個，權重為 3 放3個，最後從中隨機抽取一個出來。

抽中 i 的機率為 w[i] / total(總權重) ，所有的機率加起來會等於 1 。若把機率從頭逐一累加，保存累進序列，這序列以權重把[0,1]之間切割區間。

用 random.random() ，可以得到一個 [0, 1] 之間的 float ，然後我們要用這個 [0, 1]之間的 random數 去對應出一個 i。

以輸入[1,4]為例，對照累進機率，若 random數 位於 [0, 0.2]，那代表抽到 0 。若 random數 位於 [0.2, 1]，那代表抽到 1。

要找出 random數 落於哪個區間，可以用二分法去搜尋，預期 O(logN) Time 。(不知道random的方法是用到 O(N) Time嗎？至少二分法比O(N)快)

如果剛好落在區間界線(如 == 0.2)要算前面的 i 還是後面的 i ？其實都沒差，根據「積分」，剛好落在 0.2 的機率為 0 ，所以不會影響到權重。

Python

class Solution:

    def __init__(self, w: List[int]):
        total = sum(w)
        self.w = []
        accu = 0
        for i in range(1, len(w)):
            accu += w[i] / total
            self.w.append(accu)

    def pickIndex(self) -> int:
        l, r = 0, len(self.w)
        t = random.random()
        while l < r:
            m = (r - l)//2 + l
            if self.w[m] < t:
                l = m + 1
            else:
                r = m 
        return l

C#

public class Solution {

    double[] ws;
    Random random = new Random();
        
    public Solution(int[] w) {
        var total = w.Sum() * 1.0;
        ws = new double[w.Length];
        ws[0] = w[0] / total; 
        for(int  i = 1; i < w.Length; i++)
        {
            ws[i] = ws[i-1] + w[i] / total;
        }
    }
    
    public int PickIndex() {
        var t = random.NextDouble();
        int l = 0; int r = ws.Length;
        while(l < r)
        {
            int m = (r-l)/2 + l;
            if(ws[m] < t)
                l = m + 1;
            else
                r = m;                
        }
        return l;
    }
}