528.按权重随机选择

链接：528.按权重随机选择
难度：Medium
标签：数组、数学、二分查找、前缀和、随机化
简介：给定一个正整数数组  w ，其中  w[i]  代表下标 i  的权重（下标从 0 开始），请写一个函数  pickIndex ，它可以随机地获取下标 i，选取下标 i  的概率与  w[i]  成正比。

题解 1 - typescript

• 编辑时间：2021-08-20
• 执行用时：168ms
• 内存消耗：47.4MB
• 编程语言：typescript
• 解法介绍：前缀和进行快速查找。

class Solution {
  sums: number[] = [0];
  constructor(public w: number[]) {
    for (const num of w) this.sums.push(this.sums[this.sums.length - 1] + num);
  }
  pickIndex(): number {
    const random = this.random();
    let l = 0;
    let r = this.sums.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (this.sums[mid] <= random) l = mid + 1;
      else r = mid;
    }
    return l - 1;
  }
  random(min: number = 0, max: number = this.sums[this.sums.length - 1]): number {
    return min + ~~(Math.random() * (max - min + 1));
  }
}

题解 2 - typescript

• 编辑时间：2021-08-30
• 执行用时：240ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：利用前缀和随机取值。

class Solution {
  sums: number;
  constructor(private w: number[]) {
    this.sums = w.reduce((total, cur) => total + cur, 0);
  }
  pickIndex(): number {
    let random = this.random();
    for (let i = 0; i < this.w.length; i++) {
      const w = this.w[i];
      if (random <= w) return i;
      random -= w;
    }
    return 0;
  }
  random(min: number = 1, max: number = this.sums): number {
    return min + ~~(Math.random() * (max - min + 1));
  }
}