給定權重陣列
w，實作pickIndex()：以正比於w[i]的機率隨機回傳索引i。例如w = [1,3]時，回傳 0 的機率 1/4、回傳 1 的機率 3/4。
Example:
Input: w = [1,3]，多次呼叫 pickIndex() Output: 0 約 25%、1 約 75%
Intuition
TIP
核心思路：把權重變成前綴和，等於在數線上切出長度正比於權重的區段。隨機取 [1, total] 一個整數，用二分找它落在哪個區段（第一個 prefix[i] ≥ target）。
prefix[i]=w[0..i]的累積和；索引i對應區間(prefix[i-1], prefix[i]]- 隨機
target ∈ [1, total]，找 lower bound：第一個prefix[i] ≥ target - 建構
O(n)，每次查詢O(log n)
Approaches
⭐ Prefix Sum + Binary Search — build O(n), query O(log n) / O(n)
- Idea: 前綴和把加權抽樣化為「在累積區間上二分定位」
- Time: 建構
O(n)、每次pickIndexO(log n) - Space:
O(n)- 前綴和陣列
import kotlin.random.Random
class Solution(w: IntArray) {
private val prefix = IntArray(w.size)
private val total: Int
init {
var sum = 0
for (i in w.indices) {
sum += w[i]
prefix[i] = sum
}
total = sum
}
fun pickIndex(): Int {
val target = Random.nextInt(total) + 1 // 1..total
// lower bound：第一個 prefix[i] >= target
var lo = 0; var hi = prefix.size - 1
while (lo < hi) {
val mid = (lo + hi) ushr 1
if (prefix[mid] < target) lo = mid + 1 else hi = mid
}
return lo
}
}Note: Why [1, total] and lower bound
取 target ∈ [1, total]（含端點、不含 0）能讓每個索引的命中數正好等於其權重：索引 i 的命中區間是 prefix[i-1] < target ≤ prefix[i]，長度恰為 w[i]。用 lower bound（第一個 ≥ target）即可定位到該區間的右端點索引 i。
🔑 Takeaways
- Pattern: 前綴和 + 二分——加權隨機抽樣的標準解
- Key trick: 前綴和把抽樣轉成數線定位、
target ∈ [1,total]配 lower bound 保證機率正確。同樣的「前綴和 + 二分定位」也用於跳躍/排程類問題