前缀和应用之生成加权随机数

leetcode上有一些关于前缀和的题目，但这些题目都是基于前缀和高度抽象出来的题目，纯为了做题而做题，而非实际的应用场景。

正好今天做东西时遇到一个可以使用前缀和的场景，记录下来分享一下。

加权随机数生成算法应该是实际场景会遇到的问题。比如在小汽车指标摇号，公司年会抽奖等场景中都会用到。由于各种原因，参与抽奖的人员可能权重不一样，这时候需要根据人员的权重生成随机数。

问题描述：给定一个整数数组，nums = [2,4,3,…,1] ，其中每个元素的值为其权重，请按其权重生成相应概率的随机数，并返回其下标。

这种加权随机数的场景便是前缀和的实际应用。下面我们来看一个具体简单的例子，感受一下。

以 nums = [2,4,3,1] 为具体例子，总共4个人，其权重分别为 2,4,3,1，需要我们根据其权重生成相应概率的随机数。
比如选中2的概率为 2/(2+4+3+1) = 20%,选中4的概率为 4/(2+4+3+1) = 40%，选中3的概率为30%，选中1的概率为 10%。

正常来说，我们可以根据其权重进行拓展填充，根据其权重填充出相应的数量，比如上面填充为 [2,2,4,4,4,4,3,3,3,1]，然后在这个填充数组上取一个随机数即可，注意返回的是原数组的索引。

这种方式可以实现。但问题在于：

空间占用多。我们要根据权重拓展，如果权重跨度大，比如到几千，几万这种，会直接将原数组规模扩大千倍，万倍。
这种方式的权重只能为整数。如果权重为小数，则我们需要将其扩大成整数，这时问题会转变成问题1.

前缀和

前缀和的思想非常简单，可以简单理解为数组前i个元素的和，一种预处理方式。

比如上面例子中，我们遍历一遍数组，计算得出的前缀和数组为 [2,6,9,10]。

然后我们生成一个 [0~10) 的随机数，注意包含0，但不包含10。

此时我们根据生成的随机数，比如7，来到前缀和数组中找到第一个大于7的元素，即9，其对应的索引便是权重为3这个元素，便是要返回的元素。

原理何在？

我们生成的 [0~10) 所有可能为 0,1,2,3,4,5,6,7,8,9 总共10个数，每个数生成的概率都是一样的。

返回上面例子，我们知道选中1的概率为 10%，选中2的概率为 20%，选中3的概率为 30%，选中4的概率为 40%。

按原数组nums的顺序：
选中2的概率为 20%，对应所有可能10个数的 0,1
选中4的概率为 40%，对应所有可能10个数的 2,3,4,5
选中3的概率为 30%，对应所有可能10个数的 6，7，8
选中1的概率为 10%，对应所有可能10个数的 9

生成的随机数7对应的元素便是权重为3的这个数的索引即是需要返回的索引。

这里前缀和的本质就是，按权重计算权重区间，然后根据生成的随机数落于哪个区间返回相应区间对应的元素。

而且，由于前缀和单调递增的特性，生成随机数在前缀和中查找第一个大于随机数的元素时，还可以使用二分查找来加快查找速度。

简单的代码实现：

function weightRand(nums: number[]): number {
  const length = nums.length;
  const preSum = [nums[0]];
  for (let i = 1; i < length; i++) {
    preSum[i] = nums[i] + preSum[i - 1];
  }
  
  // 生成随机数
  const rand = Math.floor(Math.random() * preSum[length - 1]);
  
  // 这里可以用二分查找优化查找效率
  for (let i = 0; i < length; i++) {
    if (preSum[i] > rand) {
      return i;
    }
  }

  return -1;
}