在限制区域内随机取点，求比较高效的算法

Question

是这样，算法要求，每秒生成一个随机数，这个随机数必须是符合一定要求的。有什么比较高效的算法。
譬如
[0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0]
20个数组元素，采用 Math.floor(20*Math.random())，生成随机数后，需要验证，如果对应的数组元素为1，则重新生成。
一般来说，有两种算法，第一种就像我上面说的，每次生成后去验证，对应元素是否为1，这样做的弊端就是当整个数组大部分都是1的时候，生成随机数的效率很低。
还有一种算法，就是在生成之前，统计数组中数组元素不是1的个数（此处是17），然后在这17个元素里面生成一个随机数，这样的弊端就是每次生成之前都要消耗大量资源。
除了以上两种算法，还有没有更好一点的算法，能高效的生成符合要求的随机数？

Answer 1

这个问题被你描述复杂了，算法如何变得简单？思路非常重要。其实你就是想要生成20个数，同时这个20个数是从0~20之中随机生成，对不对？另外，我注意到Math.floor即取整，类似于~~双重按位非，也就是说，生成的数是整数。基于此，可简化如下为：『获取一定范围内的有限个随机整数』，生活对应的例子就是抓阄（20个人依次排队抓到自己的名字，就是20个数的一种随机顺序）。算法如下（比今年早些时候某前端架构师的代码更加高效）：

const getRandomArray = function(startNum, endNum, size) {
     //校验数据合法性
     if(typeof startNum === 'number' && typeof endNum === 'number' && endNum >= startNum && typeof size === 'number') {
          // 初始化数字数组
          const array = [...Array(endNum + 1).keys()].slice(startNum),
                 randomArray = [];
          //随机从数组中取数
          while(array.length && size--) {
               const cursor = ~~(Math.random() * array.length);
               randomArray.push(...array.splice(cursor, 1));
          }
          return randomArray;
     }
}

getRandomArray(0, 20, 20);// 这是本地运行时的一种结果 [11, 10, 5, 7, 2, 8, 13, 20, 4, 15, 16, 18, 3, 14, 12, 9, 6, 17, 1, 19]

以上，各参数分别代表：最小值，最大值，范围之内生成的随机数个数。
这个算法，本地循环1w遍也不会有压力。

Answer 2

贪吃蛇果实选点

题主在其他答案的评论里提到，这个问题来源于贪吃蛇。他只是想在未被蛇身占据的空白区域里面均匀随机取一个格子做为果实。

游戏里的蛇身不会很长（否则游戏玩就不下去了），即蛇身区域占比(p)较小。这时用“选到蛇身就从新选点”的方法（题主的方法1）是比较高效的，因为这里的随机选点次数服从几何分布，平均值为1/(1-p)。p < 0.5时也就是一两次的样子。

一般情况

若p接近于1，方法1是没有上界的。此时可用题主的方法2，即只限制在空白区域中随机选点。需要知道空白格子的个数m：

1. 随机选取1至m中的一个数字r

2. 然后遍历所有的格子，遇到空白格子则r减一

3. 当r=0时，返回当前的位置。

综合两种方法的代码如下（p<=0.5时用方法1，否则用方法2）：

random_index(a[], m)  // m is number of 0s in a[]
{
    if m/length(a) > 0.5
        while (true)
        {
            // random(k) chooses from 1, 2, ... k
            r = random(length(a));
            if !a[r-1] return r-1;
        }            
    r = random(m);
    for (i=0; i<length(a); ++i)
        if !a[i] && !(--r)
            return i;
    return -1;
}

容易看出最坏情况下复杂度为O(n)，当n和p都比较大时费时较多。这时更合理的方法应该是维护一个“空白列表”并在其中随机抽取。