按权重随机选择 图解题解

这道题到底在问什么

w

[1,3,2]

总权重

1+3+2 = 6

各下标概率

1/6, 3/6, 2/6

最优解：一步一步想明白

1. 3最直觉的做法是「按权重摊开」：1 个 0、3 个 1、2 个 2 →[0,1,1,1,2,2]，再均匀随机挑一个。思路对，但权重一大(几万)就会撑爆内存——得想个不真摊开的办法。
2. 4不真摊开，而是想象一条长度为 6 的数轴：[1] 占 (0,1]、[1] 占 (1,4]、[2] 占 (4,6]。区间越长越容易被命中——这正好等于按权重选。找「点落在哪段」用前缀和记区间右端、用二分定位。
3. 5w = [1, 3, 2]先把权重数组摆出来：[1, 3, 2]。接下来要把它累加成前缀和数组——也就是每个下标在数轴上的右端坐标。
4. 6pre[0] = w[0] = 1新建一个前缀和数组 pre。第 0 格直接抄 w[0]：pre[0]=1。它表示下标 0 的区间右端 = 1，即区间 (0,1]。
5. 7pre[1] = pre[0] + w[1] = 1+3第 1 格 = 前一格 pre[0]=1 加上 w[1]=3，得 pre[1]=4。下标 1 的区间右端 = 4，即区间 (1,4]，长度正好是它的权重 3。
6. 8pre[2] = pre[1] + w[2] = 4+2第 2 格 = pre[1]=4 加上 w[2]=2，得 pre[2]=6。这也是总权重。下标 2 占区间 (4,6]，长度 2。前缀和数组建好了：[1,4,6]。
7. 9pre = [1,4,6]，总长 6现在 pre=[1,4,6] 就是三段区间的右端坐标。把整条数轴想成 1 到 6 的 6 个整数点，每个点落在哪段、就选那个下标——点越多的段(权重越大)越容易中。
8. 10每次抽样：先掷一个 1~6 的随机数 target，然后在有序的 pre 里二分找第一个 ≥ target 的位置——这就是 target 这个点落进的区间下标。下面拿 target=4 演一遍二分。
9. 11target = 4（随机落在区间 (1,4]）假设这次随机掷出 target=4。它落在数轴的哪一段？用二分在 pre=[1,4,6] 上找第一个 ≥ 4 的格子。
10. 12lo=0, hi=n=3二分找下界：lo 指 0、hi 指 3（= n，数组外一格）。答案下标就夹在 [lo, hi) 之间，慢慢往中间收。
11. 13mid = (0+3)/2 = 1mid 落在下标 1。看 pre[mid]=pre[1]=4 与 target=4 比一比，决定往哪边收。
12. 14pre[1]=4 ≥ target=4 → 收右界pre[1]=4 ≥ target=4，说明下标 1 够大、可能就是答案，但还要看左边有没有更小的也满足，所以 hi=mid=1(保留 mid 自己，故不是 mid−1)。
13. 15hi → 1，排除下标 1 右边hi 收到 1，下标 2 变灰出局——它的右端 6 比 4 大没错，但更靠右、不会是第一个满足的。范围缩成 [0,1)。
14. 16mid = (0+1)/2 = 0新范围 [0,1) 里取中点，mid 落到下标 0。再比一次 pre[0] 和 target。
15. 17pre[0]=1 < target=4 → 收左界pre[0]=1 < target=4，下标 0 的区间右端才到 1，装不下 target=4。它出局(变灰)，lo=mid+1=1。
16. 18lo == hi，停！下标 = 1lo 和 hi 撞到一起停下，命中下标 1。target=4 确实落在区间 (1,4] 里——pickIndex() 这次返回 1。
17. 19target=4 ∈ (pre[0]=1, pre[1]=4]复核一眼：4 比 pre[0]=1 大、又 ≤ pre[1]=4，正好卡在下标 1 的区间 (1,4] 里。返回 1 无误。
18. 20target=5 → 重新二分换个随机数 target=5 再演一遍，体会二分每次怎么收。lo=0, hi=3 重新开局。
19. 21mid=(0+3)/2=1, pre[1]=4 < 5mid 落下标 1，pre[1]=4 < target=5，下标 1 的区间右端才到 4、装不下 5。下标 1 出局，lo 跳到 2。
20. 22lo=2,hi=3 → mid=2, pre[2]=6 ≥ 5范围缩到 [2,3)，mid 落下标 2，pre[2]=6 ≥ 5，下标 2 够大，hi 收到 2。
21. 23lo == hi == 2，停！lo、hi 撞在下标 2 停下，命中下标 2。target=5 落在区间 (4,6]，返回 2。
22. 24target=1 → 第一个 pre[i]≥1 是下标 0再掷一个 target=1：第一个 ≥ 1 的是 pre[0]=1，命中下标 0。6 个点里只有 1 落进 0 的区间——所以下标 0 概率 1/6，和权重对上。
23. 25target=6 → 第一个 pre[i]≥6 是下标 2再掷 target=6：第一个 ≥ 6 的是 pre[2]=6，命中下标 2。点 5、6 都落进 2 的区间(长度 2)，概率 2/6——区间越长越容易中，正是按权重。
24. 261→0 ┆ 2,3,4→1 ┆ 5,6→2把 1~6 全掷一遍：1 个点归下标 0、3 个点归下标 1、2 个点归下标 2，比例 1:3:2 正好是权重比。前缀和把权重变成了区间长度，二分让每次抽样只花 O(log n)。
25. 31「带权随机」「按频率采样」这类问题都能往这个模板靠：前缀和把离散权重摊成连续数轴，二分把一次采样压到对数级。是离线采样的经典套路。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import random, bisect
class Solution:
    def __init__(self, w):
        self.pre = []
        s = 0
        for x in w:                       # 构建前缀和
            s += x
            self.pre.append(s)
        self.total = s
    def pickIndex(self):
        target = random.randint(1, self.total)   # [1, total]
        return bisect.bisect_left(self.pre, target)  # 第一个 ≥

class Solution {
    vector<int> pre;
public:
    Solution(vector<int>& w) {
        int s = 0;
        for (int x : w) { s += x; pre.push_back(s); }  // 前缀和
    }
    int pickIndex() {
        int target = rand() % pre.back() + 1;          // [1, total]
        return lower_bound(pre.begin(), pre.end(), target) - pre.begin();
    }
};

class Solution {
    private int[] pre;
    private java.util.Random rnd = new java.util.Random();
    public Solution(int[] w) {
        pre = new int[w.length];
        int s = 0;
        for (int i = 0; i < w.length; i++) {           // 前缀和
            s += w[i];
            pre[i] = s;
        }
    }
    public int pickIndex() {
        int target = rnd.nextInt(pre[pre.length - 1]) + 1;  // [1, total]
        int lo = 0, hi = pre.length;
        while (lo < hi) {                              // 找第一个 ≥
            int mid = lo + (hi - lo) / 2;
            if (pre[mid] >= target) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

复杂度

面试官可能追问