Day 50 每日一題 Leetcode - **✍️ 528. Random Pick with Weight** 一個數組 `w` 裡面包含一些正整數。每個數字代表一個權重。 實作函數 `pickIndex()`這個函數會隨機選擇一個數組的索引並返回。選擇每個索引的機率不是平均的，而是根據權重來決定的 權重越大的索引，被選中的機會就越大。例如選中索引 i 的機率是：這個索引的權重 / 所有權重的總和 如果數組是 `[1, 3]`: - 選中索引 0 的機率是 1 / (1+3) = 25% - 選中索引 1 的機率是 3 / (1+3) = 75% **🧠 思考過程**  Brute Force: [1, 3] 建立一個 array 把每個權重對應的值放入，變成 [0, 1, 1, 1] 。 回傳 random[array] BS: [1, 3 ,2] 用 prefix sum 轉換為 [1 ,4, 6]，這時候 random (1-6)，假設數字是 2，用 BS 從 [1,4,6] 找到第一個 ≥ 2 的 idx 並回傳 T:O(n+logn) S:O(1)