求star

题目#

现有一个微信红包总金额设为m，红包个数为n(也可以理解为有n人抢红包),请设计实现一个算法，使得这 n 个红包的金额随机分配 且 保证公平(即每个红包分得的金额概率相同)

注意：不能有人空手而归，也就是分到的钱数不能为0，

示例1#

输入: m = 100, n = 10
输出: [1.48,0.41,7.36,23.43,1.17,3.17,13.22,5.83,25.15,18.78]

题解#

TIP

​ 可以将这个问题 转换为 一根长度为 m 的绳子，将它分为 n 段 ，我们很容易可以知道，将一根绳子分为n段需要分n-1次。

所以我们随机初始化n-1个位置(要切的位置)，然后排序，就可以得到每一段绳子的长度

尝试实现：#

const distribute = (money, count) => {
  // 元 => 分
  money *= 100
  const res = [] 
  let loop = count
  while (--loop) {
    // (money - 2) 是 去掉 0 和 money 两个边界
    let ran = Math.floor((money - 2) * Math.random()) + 1;
    res.push(ran)
  }
  res.sort((a, b) => a - b)
  // 因为接下来要计算每个人得到的金额 res[i] - res[i-1] ，所以要把总金额push进去
  res.push(money)
  // 计算每个人分到的金额
  for (let i = res.length - 1; i > 0; i--) {
    res[i] = (res[i] - res[i - 1])
  }
  // 最后将结果换算回元
  return res.map(item => item / 100)
}

distribute(0.1,10);
// 输出结果: [
  0.01, 0.03,    0,
     0, 0.01, 0.01,
  0.01, 0.01,    0,
  0.02
]

最终题解:key:#

TIP

​ 避免出现分到0的情况，并添加判断条件

/**
 * @param {Number} money 红包总金额(元)
 * @param {Number} count 红包个数
 * @return {Array} 每个人分到的钱数
 */
const distribute = (money, count) => {
  // 元 => 分
  money *= 100;
  if (money / count < 1) {
    return new Error('每个红包至少0.01元!');
  }
  // 初始化可能分到的所有可能金额
  const arr = new Array(money).fill(0).map((_, i) => i);
  let loop = count;
  while (--loop) {
    // (money - 2) 是 去掉 0 和 money 两个边界
    let ran = Math.floor((money - 2) * Math.random()) + 1;
    [arr[loop], arr[ran]] = [arr[ran], arr[loop]];
  }
  let res = arr.slice(1, count);
  res.sort((a, b) => a - b);
  // 因为接下来要计算每个人得到的金额 res[i] - res[i-1] ，所以要把总金额push进去
  res.push(money);
  // 计算每个人分到的金额
  for (let i = res.length - 1; i > 0; i--) {
    res[i] = (res[i] - res[i - 1]);
  }
  // 最后将结果换算回元
  return res.map(item => item / 100);
};