主題
題目連結：
題目意譯：
你被給定一的正整數陣列 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 ，而其他索引值同理。因此符合題目的權重隨機分布。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
