题目描述
思路

leetcode - daily - 528. 按权重随机选择

August 30, 2021

题目描述

给定一个正整数数组 w ,其中 w[i] 代表下标 i 的权重(下标从 0 开始),请写一个函数 pickIndex ,它可以随机地获取下标 i,选取下标 i 的概率与 w[i] 成正比。

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

也就是说,选取下标 i 的概率为 w[i] / sum(w) 。

 

示例 1:

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

输入:
["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 <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-with-weight
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

几何随机

  1. 构建线段,根据 weight 计算每个节点在线段上的长度占比
  2. 在线段上生成随机数 x, 看 x 落在线段上位置
  3. 根据位置计算生成的随机索引

/**
 * @param {number[]} w
 */
var Solution = function (w) {
  let sum = 0,
    weights = [];

  for (let v of w) {
    sum += v;
    weights.push(sum);
  }

  this.weights = weights;
  this.sum = sum;
};

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function () {
  const { sum, weights } = this;
  let randomNum = Math.floor(Math.random() * sum);
  for (let i = 0; i < weights.length; i++) {
    if (weights[i] > randomNum) {
      return i;
    }
  }
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(w)
 * var param_1 = obj.pickIndex()
 */
  • 时间复杂度: $O(N)$, N 为 weights 长度
  • 空间复杂度: $O(N)$, N 为 weights 长度

feiker 少年起而行之