✨ 数组洗牌与随机采样 👌

• 快速上手
• 面试核心问题：如何实现公平的数组洗牌算法
  • 常见错误解法及缺陷
  • 面试官核心考察点
• 满分解法：费雪耶兹（Fisher–Yates）洗牌
  • 算法核心逻辑
  • 代码实现
  • 公平性数学证明（数学归纳法）
• 算法进阶应用：随机抽取 K 个不重复元素
  • 应用场景
  • 实现逻辑与代码
• 面试答题总结

要点速览

• 公平洗牌首选 Fisher–Yates：时间 O(n)、空间 O(1)、原地交换，概率均匀。
• 误区：array.sort(() => Math.random() - 0.5) 不公平且时间复杂度为 O(n log n)。
• 随机采样 K 个不重复元素：执行洗牌的前 K 次迭代或用蓄水池采样（流式场景）。
• 实战建议：封装 shuffle 与 sampleK，提供可选 rng 与种子，便于测试与回放。

快速上手

最小可用实现与用法示例：

// Fisher–Yates 洗牌（原地操作）
export function shuffle(array, rng = Math.random) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(rng() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

// 采样 K 个不重复元素（拷贝 + 前 K 次迭代）
export function sampleK(arr, k, rng = Math.random) {
  const copy = [...arr];
  const n = copy.length;
  if (k > n) throw new Error("k 不能大于数组长度");
  for (let i = 0; i < k; i++) {
    const j = Math.floor(rng() * (n - i)) + i; // [i, n-1]
    [copy[i], copy[j]] = [copy[j], copy[i]];
  }
  return copy.slice(0, k);
}

// 使用示例
console.log(shuffle([1, 2, 3, 4, 5]));
console.log(sampleK(["A", "B", "C", "D", "E"], 3));

正确心智模型

• “公平”指算法对每个排列/位置的概率一致，前提是 RNG 近似均匀（Math.random 非加密但足够面试）。
• 采样的前 K 次迭代等价于“把随机元素放到前面”，无需全量洗牌，复杂度 O(k)。

面试核心问题：如何实现公平的数组洗牌算法

常见错误解法及缺陷

• 错误解法：使用数组sort方法结合Math.random()实现洗牌
• 两大致命缺陷
  1. 概率不公平：数学上无法保证每个元素出现在任意位置的概率相等（因 V8 引擎随机性存在偏向）
  2. 性能较差：排序算法时间复杂度通常为O(n log n)，不符合高效要求

面试官核心考察点

考察维度	具体要求
概率公平	洗牌后数组每个元素出现在任意位置的概率必须为1/N（N 为数组长度），无随机性偏差，最好能提供数学证明
时空复杂度	时间复杂度需为线性O(n)，且为原地操作（空间复杂度O(1)），无需创建新数组浪费内存

满分解法：费雪耶兹（Fisher–Yates）洗牌

算法核心逻辑

• 核心思想：倒序遍历 + 随机交换
• 四步执行流程
  1. 从数组最后一个元素（索引array.length - 1）开始向前遍历
  2. 在[0, I]区间（包含当前遍历索引I）内随机生成一个索引J
  3. 交换数组中第I个元素与第J个元素
  4. 索引I减 1，重复上述步骤，直至遍历完整个数组

代码实现

function shuffleArray(array) {
  // 1. 倒序遍历：从数组末尾开始，遍历至索引1（I > 0）
  for (let i = array.length - 1; i > 0; i--) {
    // 2. 生成随机索引J：范围[0, i]，乘以i+1确保包含i，Math.floor向下取整
    const j = Math.floor(Math.random() * (i + 1));
    // 3. ES6解构赋值交换元素，实现原地操作
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

公平性数学证明（数学归纳法）

• 步骤 1：证明最后一个位置（索引 N-1）
  遍历到最后一个元素时，该元素会与[0, N-1]区间内任意元素交换，任意元素留在该位置的概率为1/N。
• 步骤 2：证明倒数第二个位置（索引 N-2）
  元素要留在该位置，需满足两个条件：
  1. 上一轮（处理最后一个元素时）未被选中交换，概率为(N-1)/N；
  2. 本轮（处理倒数第二个元素时）从剩余N-1个元素中被选中，概率为1/(N-1)；
  3. 总概率：(N-1)/N * 1/(N-1) = 1/N。
• 步骤 3：归纳推广
  以此类推，任意元素出现在任意位置的概率均为1/N，算法满足公平性要求。

可复现实验与校验（面试加分）

• 频次统计：对长度为 4 的数组执行 10000 次洗牌，统计每个元素出现在每个位置的次数应近似相等。
• 简易实现：

const N = 4;
const RUNS = 10000;
// 初始化位置统计数组，pos[i][j]表示元素i出现在位置j的次数
const pos = Array.from({ length: N }, () => Array(N).fill(0));
for (let r = 0; r < RUNS; r++) {
  const a = shuffle([0, 1, 2, 3]);
  for (let i = 0; i < N; i++) pos[a[i]][i]++;
}
// 每个元素在每个位置出现的次数应接近 RUNS/N
console.table(pos);

算法进阶应用：随机抽取 K 个不重复元素

应用场景

如“从 100 个用户中随机抽取 3 个中奖者”，本质是洗牌算法的简化版。

实现逻辑与代码

• 核心思路：仅执行费雪耶兹洗牌算法的前K次迭代，数组前K个元素即为结果。
• 代码实现

function randomSample(array, k) {
  // 拷贝新数组，避免修改原数组
  const copy = [...array];
  const n = copy.length;
  // 仅执行前K次迭代（遍历0到k-1）
  for (let i = 0; i < k; i++) {
    // 从[i, n-1]区间随机选索引（范围随迭代缩小）
    const j = Math.floor(Math.random() * (n - i)) + i;
    // 交换当前i位置与随机j位置的元素
    [copy[i], copy[j]] = [copy[j], copy[i]];
  }
  // 截取前K个元素作为采样结果
  return copy.slice(0, k);
}

进阶：蓄水池采样（未知 N 的流式场景）

当元素总数 N 未知或数据以流形式到达时，可使用蓄水池采样（Reservoir Sampling）：

/**
 * 蓄水池采样
 * 从未知长度/流式数据中均匀采样 k 个元素。
 * - 目标：保证每个元素被选中的概率均为 k / N（N 为总元素数）。
 * - 适用：N 很大或无法一次性加载的数据源（迭代器、生成器、流）。
 * 参数：
 * - iterable：可迭代的数据源
 * - k：需要采样的元素个数（k ≥ 0）
 * - rng：随机数函数，返回 [0, 1) 的近似均匀随机数，默认 Math.random
 * 复杂度：时间 O(N)，空间 O(k)
 */
function reservoirSample(iterable, k, rng = Math.random) {
  const res = [];
  let i = 0; // 已处理的元素个数（从 0 开始计数）
  for (const item of iterable) {
    if (i < k) {
      // 前 k 个元素直接放入蓄水池
      res[i] = item;
    } else {
      // 第 i 个元素以 k/(i+1) 的概率进入蓄水池：
      // 在 [0, i] 均匀选 j，若 j < k 则替换蓄水池中第 j 个元素。
      // 该设计保证每个元素最终等概率被保留在蓄水池中。
      const j = Math.floor(rng() * (i + 1)); // j ∈ [0, i]
      if (j < k) res[j] = item;
    }
    i++;
  }
  return res;
}

• 思想：前 K 个直接入池；第 i 个元素以 k/(i+1) 的概率替换池中某元素，保证每个元素等概率被选中。

面试答题总结

1. 算法核心：明确费雪耶兹算法的核心是“倒序遍历”；
2. 关键操作：强调“在[0, I]区间内随机选择元素并交换”；
3. 时空复杂度：说明算法是“原地操作”，时间复杂度O(n)、空间复杂度O(1)；
4. 扩展加分：可主动提及算法的进阶应用——随机采样（执行前K次迭代），体现对算法的深度理解。