主題

LeetCode - 528. Random Pick with Weight 解題心得

Not In My Back Yard | 2021-09-13 00:00:01 | 巴幣 2 | 人氣 46

題目連結:


題目意譯:
你被給定一的正整數陣列 w 其中 w[i] 代表著索引值 i (索引值從 0 開始)的權重。

我們需要呼叫函式 pickIndex() 其將隨機地回傳一個位於範圍 [0, w.length - 1] 之整數。 pickIndex() 之回傳應正比於 w 陣列中的權重。例如,對於 w = [1, 3] ,挑到索引值 0 的機率為 1 ÷ (1 + 3) = 0.25(即 25%)而挑到索引值 1 的機率為 3 ÷ (1 + 3) = 0.75(即 75%)。

更正式地說,挑到索引值 i 的機率為 w[i] ÷ sum(w) 。

限制:
1 ≦ w.length ≦ 10000
1 ≦ w[i] ≦ 10 ^ 5
pickIndex 最多只會被呼叫 1000 次。



範例測資:
範例 1:
輸入
["Solution","pickIndex"]
[[[1]],[]]
輸出
[null,0]
解釋
Solution solution = new Solution([1]);
solution.pickIndex(); // 回傳 0 。因為陣列就只有這麼一個元素,所以唯一選擇為回傳其第一個元素。

範例 2:
輸入
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
輸出
[null,1,1,1,1,0]
解釋
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 回傳 1 。其回傳了第二個元素(索引值 = 1),其有著機率 ¾ 。
solution.pickIndex(); // 回傳 1 。return 1
solution.pickIndex(); // 回傳 1 。return 1
solution.pickIndex(); // 回傳 1 。return 1
solution.pickIndex(); // 回傳 0 。其回傳了第一個元素(索引值 = 1),其有著機率 ¼ 。

由於這是個隨機化的問題,因此允許有多重的答案,所以以下輸出被視為是正確的:
[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]
……
等等。


解題思維:
假設 w 中所有元素和為 T 。則我們可以將
範圍 [0, w[0]) 丟給 w[0] 、
[w[0], w[0] + w[1]) 丟給 w[1] 、
…… 、
[w[0] + …… + w[w.length - 2], T) 丟給 w[length - 1]
而可以看到每個區間的長度依序為 w[0] 、 w[1] 、 …… w[w.length - 1] 。

接著我們按照這題的棄卻抽樣(Rejection Sampling)之作法,挑出位於 0 ~ T - 1 之間的一個整數,然後看此整數位於哪個範圍之中,即是挑到哪個索引值。

而這樣一來,例如,落在 [w[0], w[0] + w[1]) 的機率將是 w[1] ÷ T ,而其他索引值同理。因此符合題目的權重隨機分布。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作