一道常被人轻视的web前端常见面试题(JS)

一道常被人轻视的web前端常见面试题(JS) 完整攻略

题目描述

假设有一个 getRandom() 函数可以随机生成 0 ~ 9 之间的整数，请编写一个 getRandomArray(n) 函数，返回长度为 n 的由随机整数组成的数组。

解题思路

这道题看起来比较简单，只需要使用 for 循环调用一遍 getRandom 函数，然后存储到结果数组中即可。具体实现如下：

function getRandom() {
  return Math.floor(Math.random() * 10)
}

function getRandomArray(n) {
  const res = []
  for (let i = 0; i < n; i++) {
    res.push(getRandom())
  }
  return res
}

注意点

但是这种实现方式有一个问题，如果生成长度超过 10 的随机数组，会导致有些数字无法出现。比如，若要生成长度为 11 的随机数组，那么必有一个数字无法出现。因此，这种方式并不是十分完美。

针对这个问题，我们可以使用洗牌算法。这个算法是一种在线性时间复杂度内把数组中元素打乱排序的算法。其实现方式如下：

1. 初始化当前位置 currentIndex 为数组长度 array.length - 1
2. 初始化交换位置的变量 temporaryValue
3. 随机选择一个位置 randomIndex
4. 用 array[randomIndex] 和 array[currentIndex] 交换位置
5. 减少 currentIndex 的值，重复步骤 3 ~ 5 直到随机出当前元素

这样就可以保证随机数组生成的每个数字都会出现。

洗牌实现

function shuffle(array) {
  let currentIndex = array.length
  let temporaryValue, randomIndex

  while (currentIndex !== 0) {
    randomIndex = Math.floor(Math.random() * currentIndex)
    currentIndex--

    temporaryValue = array[currentIndex]
    array[currentIndex] = array[randomIndex]
    array[randomIndex] = temporaryValue
  }

  return array
}

然后，我们把 getRandomArray 函数改为：

function getRandomArray(n) {
  const res = []
  for (let i = 0; i < n; i++) {
    res.push(i)
  }
  return shuffle(res).slice(0, n)
}

示例说明

下面我们运行一下示例代码，验证一下结果：

const arr = getRandomArray(10)
console.log(arr) // => [4, 1, 6, 2, 5, 0, 8, 3, 9, 7]

总结

通过洗牌算法，我们可以生成一个随机数据集合，每个元素概率相等。所以，它是一个有效的满足大多数需求的随机数字生成算法。通过本题，让我们学会了如何在 JS 中完美地生成随机数数组。