怎么在制定数据源里面生成一个长度为 n 的不重复随机数组 能有几种方法 时间复杂度多少（字节）

[Sunny-117]

尽量用较低的时间复杂度实现

[Ha0ran2001]

洗牌算法

function fisherYates(source, n) {
  if (n > source.length) {
    throw new Error('需要的长度超过了数据源大小')
  }

  // 复制原数组，避免修改原数据
  const copy = [...source]

  // Fisher-Yates洗牌算法
  for (let i = copy.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1))
    ;[copy[i], copy[j]] = [copy[j], copy[i]]
  }

  return copy.slice(0, n)
}

随机抽样不放回

function generateRandomArrayByPickAndRemove(source, n) {
  if (n > source.length) {
    throw new Error('需要的长度超过了数据源大小')
  }

  const result = []
  const usedIndices = new Set()

  while (result.length < n) {
    const randomIndex = Math.floor(Math.random() * source.length)
    if (!usedIndices.has(randomIndex)) {
      usedIndices.add(randomIndex)
      result.push(source[randomIndex])
    }
  }

  return result
}

Set实现

function generateRandomArrayBySet(source, n) {
  if (n > source.length) {
    throw new Error('需要的长度超过了数据源大小')
  }

  const resultSet = new Set()

  while (resultSet.size < n) {
    const randomIndex = Math.floor(Math.random() * source.length)
    resultSet.add(source[randomIndex])
  }

  return Array.from(resultSet)
}

function generateRandomArrayByReservoir(source, n) {
  if (n > source.length) {
    throw new Error('需要的长度超过了数据源大小')
  }

  // 前n个元素直接放入结果
  const result = source.slice(0, n)

  // 对剩余元素进行Reservoir抽样
  for (let i = n; i < source.length; i++) {
    const j = Math.floor(Math.random() * (i + 1))
    if (j < n) {
      result[j] = source[i]
    }
  }

  return result
}