0528. 按权重随机选择【中等】

1. 📝 题目描述
2. 🎯 s.1 - 前缀和 + 二分查找

1. 📝 题目描述

leetcode

给你一个下标从 0 开始的正整数数组 w，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex，它可以随机地从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率为 w[i] / sum(w)。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

示例 1：

txt

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

txt

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[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]
......
诸若此类。

提示：

1 <= w.length <= 10^4
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10^4 次

2. 🎯 s.1 - 前缀和 + 二分查找

cjspy

typedef struct {
    int* prefix;
    int size;
    int total;
} Solution;

Solution* solutionCreate(int* w, int wSize) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->prefix = (int*)malloc(sizeof(int) * wSize);
    obj->size = wSize;
    int sum = 0;
    for (int i = 0; i < wSize; i++) { sum += w[i]; obj->prefix[i] = sum; }
    obj->total = sum;
    return obj;
}

int solutionPickIndex(Solution* obj) {
    int target = rand() % obj->total + 1;
    int lo = 0, hi = obj->size - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (obj->prefix[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

void solutionFree(Solution* obj) { free(obj->prefix); free(obj); }

/**
 * @param {number[]} w
 */
var Solution = function (w) {
  this.prefix = []
  let sum = 0
  for (const val of w) {
    sum += val
    this.prefix.push(sum)
  }
  this.total = sum
}

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function () {
  const target = Math.floor(Math.random() * this.total) + 1
  let lo = 0,
    hi = this.prefix.length - 1
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (this.prefix[mid] < target) lo = mid + 1
    else hi = mid
  }
  return lo
}

class Solution:
    def __init__(self, w: List[int]):
        self.prefix = []
        total = 0
        for val in w:
            total += val
            self.prefix.append(total)
        self.total = total

    def pickIndex(self) -> int:
        target = random.randint(1, self.total)
        return bisect_left(self.prefix, target)

时间复杂度：初始化 $O (n)$ ，每次 pickIndex $O (\log n)$
空间复杂度： $O (n)$

算法思路：

构建权重前缀和数组
随机一个 $[1, t o t a l]$ 的数，二分查找定位到对应下标

⏰0528. 按权重随机选择【中等】

0528. 按权重随机选择【中等】 ​

1. 📝 题目描述 ​

2. 🎯 s.1 - 前缀和 + 二分查找 ​

0528. 按权重随机选择【中等】

1. 📝 题目描述

2. 🎯 s.1 - 前缀和 + 二分查找