LeetCode 528. 按权重随机选择

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 二分查找（推荐）
相似题目

题目描述

✅ 528. 按权重随机选择

思路分析

解法一：前缀和 + 二分查找（推荐）

核心思路：

构建前缀和数组 prefixSum，其中 prefixSum[i] 表示权重数组前 i 个元素的累计和。

调用 pickIndex() 时，在 [1, total] 范围内生成一个随机整数 rand，其中 total 为所有权重之和。

通过二分查找，找到第一个满足 prefixSum[i] >= rand 的下标 i，即为按权重随机选取的结果。

权重越大，对应区间越长，被随机数命中的概率也越高，从而实现按权重随机选择。

复杂度分析：

时间复杂度：O(n) 初始化，O(log n) 查询，其中 n 为权重数组长度。

空间复杂度：O(n)，用于存储前缀和数组。

class Solution {

    // 前缀和数组
    private int[] prefixSum;
    // 权重总和
    private int total;
    private Random random;

    public Solution(int[] w) {
        prefixSum = new int[w.length];
        random = new Random();
        // 构建前缀和数组
        for (int i = 0; i < w.length; i++) {
            prefixSum[i] = (i == 0 ? 0 : prefixSum[i - 1]) + w[i];
        }
        total = prefixSum[w.length - 1];
    }

    public int pickIndex() {
        // 在 [1, total] 范围内随机生成整数
        int rand = random.nextInt(total) + 1;
        // 二分查找第一个 >= rand 的前缀和位置
        int lo = 0, hi = prefixSum.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefixSum[mid] < rand) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

type Solution struct {
    // 前缀和数组
    prefixSum []int
    // 权重总和
    total int
}

func Constructor(w []int) Solution {
    prefixSum := make([]int, len(w))
    // 构建前缀和数组
    for i, v := range w {
        if i == 0 {
            prefixSum[i] = v
        } else {
            prefixSum[i] = prefixSum[i-1] + v
        }
    }
    return Solution{
        prefixSum: prefixSum,
        total:     prefixSum[len(w)-1],
    }
}

func (s *Solution) PickIndex() int {
    // 在 [1, total] 范围内随机生成整数
    rand := rand.Intn(s.total) + 1
    // 二分查找第一个 >= rand 的前缀和位置
    lo, hi := 0, len(s.prefixSum)-1
    for lo < hi {
        mid := lo + (hi-lo)/2
        if s.prefixSum[mid] < rand {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

相似题目

题目	难度	考察点
382. 链表随机节点	中等	蓄水池抽样、随机化
398. 随机数索引	中等	蓄水池抽样、哈希表
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表、随机化
710. 黑名单中的随机数	困难	哈希表、随机化
497. 非重叠矩形中的随机点	中等	前缀和、二分查找、随机化
153. 寻找旋转排序数组中的最小值	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17386994