实现一个加权随机函数

[Vitaminaq]

此函数接收一个整数数组 input, 此数组：

1. 元素个数 N < 10000
2. 元素的值大于 0 且小于 100

返回一个随机函数, 此随机函数:

1. 返回 [0, N - 1] 之间的一个随机整数
2. 每个整数 i 被返回的概率为:数组 input 的第 i 个元素的值 / 数组 arr 的所有元素之和

例: 给定一个数组 input, 值为 [4, 2, 1, 3],调用 createWeightedRandom(input), 应当返回一个函数, 
此函数返回一个 0 - 3 之间的一个随机整数, 相应的概率分别为: 4/10, 2/10, 1/10, 3/10.

分别按以下两种要求实现该函数:

1. 空间复杂度不限, 返回的随机函数时间复杂度 O(1)
2. 空间复杂度 O(N), 返回的随机函数时间复杂度 O(logN)

[Vitaminaq]

1. 空间复杂度不限, 返回的随机函数时间复杂度 O(1)

   function createWeightedRandom_O1(input) {
   const len = input.length;
   return function() {
   const list = [];
   let total = 0;
   for (let i = 0; i < len; i++) {
       total = total + input[i];
       Array.prototype.push.apply(list, new Array(input[i]).fill(i));
   }
   return list[Math.floor(Math.random() * total)];
   }
   }

2. 空间复杂度 O(N), 返回的随机函数时间复杂度 O(logN)
   参考链接