从指定数据源生成长度为 n 的不重复随机数组

问题

给定一个数据源数组，如何从中随机抽取 n 个不重复的元素组成新数组？需要考虑多种实现方案，并分析各自的时间复杂度。

解答

方法一：Fisher-Yates 洗牌算法（推荐）

/**
 * 使用 Fisher-Yates 洗牌算法生成不重复随机数组
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
function getRandomArray1(source, n) {
  if (n > source.length) {
    throw new Error('n 不能大于数据源长度');
  }
  
  // 复制原数组，避免修改原数据
  const arr = [...source];
  const result = [];
  
  // 只需要洗牌前 n 个元素
  for (let i = 0; i < n; i++) {
    // 从剩余元素中随机选择一个索引
    const randomIndex = i + Math.floor(Math.random() * (arr.length - i));
    // 交换当前位置和随机位置的元素
    [arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]];
    result.push(arr[i]);
  }
  
  return result;
}

方法二：Set 去重法

/**
 * 使用 Set 去重生成不重复随机数组
 * 时间复杂度：O(n) ~ O(n²)（取决于碰撞概率）
 * 空间复杂度：O(n)
 */
function getRandomArray2(source, n) {
  if (n > source.length) {
    throw new Error('n 不能大于数据源长度');
  }
  
  const result = new Set();
  const len = source.length;
  
  // 当 n 接近 source.length 时，效率会降低
  while (result.size < n) {
    const randomIndex = Math.floor(Math.random() * len);
    result.add(source[randomIndex]);
  }
  
  return Array.from(result);
}

方法三：标记法（索引标记）

/**
 * 使用标记法生成不重复随机数组
 * 时间复杂度：O(n)
 * 空间复杂度：O(m)，m 为数据源长度
 */
function getRandomArray3(source, n) {
  if (n > source.length) {
    throw new Error('n 不能大于数据源长度');
  }
  
  const result = [];
  const used = new Set(); // 记录已使用的索引
  const len = source.length;
  
  while (result.length < n) {
    const randomIndex = Math.floor(Math.random() * len);
    
    if (!used.has(randomIndex)) {
      used.add(randomIndex);
      result.push(source[randomIndex]);
    }
  }
  
  return result;
}

方法四：数组splice法

/**
 * 使用 splice 删除已选元素
 * 时间复杂度：O(n²)（splice 操作为 O(n)）
 * 空间复杂度：O(n)
 */
function getRandomArray4(source, n) {
  if (n > source.length) {
    throw new Error('n 不能大于数据源长度');
  }
  
  const arr = [...source];
  const result = [];
  
  for (let i = 0; i < n; i++) {
    const randomIndex = Math.floor(Math.random() * arr.length);
    // splice 会改变数组长度，时间复杂度 O(n)
    result.push(...arr.splice(randomIndex, 1));
  }
  
  return result;
}

方法五：排序法

/**
 * 先打乱顺序再截取
 * 时间复杂度：O(m log m)，m 为数据源长度
 * 空间复杂度：O(m)
 */
function getRandomArray5(source, n) {
  if (n > source.length) {
    throw new Error('n 不能大于数据源长度');
  }
  
  return [...source]
    .sort(() => Math.random() - 0.5) // 注意：这种排序不是真正的随机
    .slice(0, n);
}

使用示例

// 准备数据源
const dataSource = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const n = 5;

// 方法一：Fisher-Yates（推荐）
console.log('方法一:', getRandomArray1(dataSource, n));
// 输出示例: [3, 7, 1, 9, 4]

// 方法二：Set 去重
console.log('方法二:', getRandomArray2(dataSource, n));
// 输出示例: [5, 2, 8, 1, 6]

// 方法三：标记法
console.log('方法三:', getRandomArray3(dataSource, n));
// 输出示例: [10, 3, 7, 2, 5]

// 方法四：splice 法
console.log('方法四:', getRandomArray4(dataSource, n));
// 输出示例: [4, 9, 1, 6, 3]

// 方法五：排序法
console.log('方法五:', getRandomArray5(dataSource, n));
// 输出示例: [2, 8, 4, 10, 1]

// 性能测试
const largeSource = Array.from({ length: 10000 }, (_, i) => i);
console.time('Fisher-Yates');
getRandomArray1(largeSource, 1000);
console.timeEnd('Fisher-Yates');

关键点

• 方法一（Fisher-Yates）是最优解：时间复杂度 O(n)，随机性好，适合所有场景

• 时间复杂度对比：

  • Fisher-Yates: O(n) - 最优
  • Set 去重法: O(n) ~ O(n²) - 当 n 接近数据源长度时性能下降
  • 标记法: O(n) - 但常数因子较大
  • splice 法: O(n²) - 不推荐
  • 排序法: O(m log m) - 对整个数据源排序，浪费性能

• 空间复杂度考虑：所有方法都需要 O(n) 的额外空间存储结果

• 随机性问题：sort(() => Math.random() - 0.5) 不是真正的随机排序，存在偏差

• 边界处理：需要判断 n 是否大于数据源长度，避免死循环

• 实际应用建议：

  • n 较小时：优先使用 Fisher-Yates
  • n 接近数据源长度时：Fisher-Yates 依然是最优选择
  • 不需要修改原数组：记得使用扩展运算符复制数组