双指针技巧

随机算法

这类题为什么特别

随机算法有个别处没有的性质：写错了也看不出来。

排序错了，输出一眼就是乱的。洗牌错了，输出依然是乱的 —— 只是某些排列出现得比另一些频繁一点。你必须跑几十万次统计频率才能发现。

⭐ 所以这一篇里的每个数字都是枚举或实测出来的，不是推的。

🚨 而这条纪律有个盲区，本篇复核时被抓到两次：出错的从来不是那些数字，而是「没有数字、只有一句话」的地方 —— 「相加是三角分布所以中间更常见」、「前 k 个永远不会被替换」，两处都是顺口推的，两处都反了。 👉 判据：一篇宣称「都实测过」的文章，要重点查的正是它没给数字的那些句子。

Fisher-Yates 洗牌

function shuffle(nums) {
  for (let i = 0; i < nums.length; i++) {
    // 🚨 j 从 i 开始，不是从 0
    const j = i + Math.floor(Math.random() * (nums.length - i));
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  return nums;
}

含义：第 i 轮从还没定下来的那部分 [i, n) 里随机挑一个，放到位置 i。挑完这一位就固定了，不再参与后面的抽取。

🚨 `j` 从 0 开始就不均匀了 —— 而且能精确算出来

常见的错法是让 j 在整个数组里随机：

const j = Math.floor(Math.random() * nums.length);   // ❌

看着更「随机」，其实不可能均匀。一个不用统计的证明：

n = 3 时，这个写法有 3 × 3 × 3 = 27 条等概率的执行路径，要映射到 3! = 6 种排列上。27 不能被 6 整除，所以必然有的排列多、有的少。

把 27 条路径全部枚举出来：

正确（j 从 i 开始）：6 条路径
  123:1/6  132:1/6  213:1/6  231:1/6  312:1/6  321:1/6     ✅ 完全均匀

错误（j 从 0 开始）：27 条路径
  123:4/27  132:5/27  213:5/27  231:5/27  312:4/27  321:4/27

⚠️ 最常见的排列出现 5/27 ≈ 18.5%，最少见的 4/27 ≈ 14.8% —— 相差 25%。洗一副牌你完全看不出来，但它确实是偏的。

📌 记法：Fisher-Yates 的路径数恰好是 n!（第 i 轮有 n-i 种选择），和排列数一一对应，所以均匀是必然的。错法的路径数是 n^n，对不上。

水塘抽样：流的长度未知

题意：一个数据流，长度事先不知道（可能很大，装不进内存），要等概率地取出 k 个元素。

k = 1 的版本：

function reservoirOne(stream) {
  let res = null;
  let i = 0;
  for (const x of stream) {
    // 第 i 个元素（0-indexed）以 1/(i+1) 的概率替换掉当前保留的
    if (Math.floor(Math.random() * (i + 1)) === 0) res = x;
    i++;
  }
  return res;
}

⭐ 为什么每个元素的概率都是 1/n：第 i 个元素被选中，需要它自己被选（概率 1/(i+1)），且之后每一个都没有替换掉它：

1/(i+1) × (i+1)/(i+2) × (i+2)/(i+3) × … × (n-1)/n = 1/n

中间的项全部约掉，剩下 1/n。

实测（流长 5，60 万次；把 Math.random 换成可播种的 mulberry32(20260907) 才复现得了 —— 用 Math.random 报出来的单个数字，读者永远核对不了）：

0.1998  0.2008  0.2003  0.1990  0.2002        理论 0.2000
最大偏差 0.0010

k > 1 的版本：

function reservoirK(stream, k) {
  const res = [];
  let i = 0;
  for (const x of stream) {
    if (i < k) res.push(x);                          // 前 k 个直接装进去
    else {
      const j = Math.floor(Math.random() * (i + 1)); // 0 .. i
      if (j < k) res[j] = x;                         // 命中就替换第 j 个
    }
    i++;
  }
  return res;
}

实测（流长 10，取 3 个，30 万次，mulberry32(31415)）：每个元素的入选频率都在 0.2988 ~ 0.3009，理论值 k/n = 0.3，最大偏差 0.0012。

🚨 注意 j 的范围是 0 .. i（共 i+1 个），不是 0 .. k-1。

写成后者会怎样？关键在于 if (j < k) 这个判断变成了永真 —— 于是每一个后来的元素都必然替换掉水塘里的某一个。后果是入选概率沿流的方向几何递增，闭式解：

前 k 个        ((k-1)/k)^(n-k)
第 i 个(i≥k)   ((k-1)/k)^(n-1-i)

流长 10、取 3 个，实测与闭式解逐格吻合：

元素   0      1      2      3      4      5      6      7      8      9
概率  .059   .059   .058   .088   .131   .198   .296   .444   .667  1.000
闭式  .0585  .0585  .0585  .0878  .1317  .1975  .2963  .4444  .6667 1.0000

⭐ 最后一个元素必然入选（概率 1），而前 k 个反而是最低的那一档。 （这一节以前写的是「前 k 个永远不会被替换、入选概率是 1」——方向正好写反了。 j 恒小于 k 意味着前 k 个位置是「总被替换的目标」，不是「永不被替换」。）

📌 而这个错法最阴险的地方没变：输出始终是「一组 k 个元素」，形状完全正常，只有统计几十万次才看得出概率是斜的。

rand7 → rand10：拒绝采样

题意：给一个等概率返回 1~~7 的 rand7()，实现等概率返回 1~~10 的 rand10()。

🚨 想当然的写法都是错的。比如 (rand7() + rand7()) % 10 + 1。它只有 49 条等概率路径，全枚举出来就看清了偏在哪：

值    1    2    3    4    5    6    7    8    9   10
/49   5    4    4    4    4    4    5    6    7    6

最常见的是 9（7/49 = 14.3%），最少见的是 2~6（4/49 = 8.2%），极差 1.75 倍。

⚠️ 这里有个容易顺口说错的地方（这一节以前就写错了）：两个均匀分布相加确实是三角分布（和为 8 时最多，7/49），但 % 10 会把它折叠一次 —— 和 10~~14 被折回到值 1~~5，正好把低端填平成一样高，只有和 7、8、9（→ 值 8、9、10）没有折叠对象、保住了三角的峰。 ⇒ 所以不是「中间的值更常见」，而是偏后的 8/9/10 更常见、中间的 5/6 最少见。

📌 判据：% 之后的分布要重新算一遍，别用取模之前的形状去描述它。

正确思路两步：先造一个更大的均匀分布，再把它裁到 10 的倍数。

function rand10() {
  for (;;) {
    const row = rand7(), col = rand7();
    const idx = (row - 1) * 7 + col;      // 均匀落在 1..49
    if (idx <= 40) return 1 + (idx - 1) % 10;   // 只要前 40 个
    // 41..49 直接丢掉重来
  }
}

⭐ 两个 rand7 组成一个 7×7 的格子，49 个格子等概率。 49 不是 10 的倍数，所以砍掉最后 9 个，剩下 40 个正好是 4 组 10。

🚨 必须丢弃并重试，不能把 41~49 映射到某几个数上 —— 那样那几个数就会多出概率。这就是「拒绝采样」这个名字的来由。

⚠️ 循环理论上可能永远不结束（每轮有 9/49 的概率重来），但期望次数是有限的：每轮成功率 40/49，期望调用 rand7 的次数是 2 ÷ (40/49) = 2.45 次。

实测 40 万次（mulberry32(777)）：1~10 的频率都在 0.0994 ~ 0.1007，平均调用 rand7 2.451 次 —— 与理论值 2.450 吻合。

📌 面试被问「会不会死循环」，答这一条：不会，期望 2.45 次调用。说得出这个数字比说「概率上会结束」有说服力得多。

这一章到此为止

双指针四篇（数组双指针、滑动窗口、二分搜索、随机算法）齐了。往下按依赖走是递归与二叉树—— 全书的枢纽。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

384. 打乱数组中等Fisher-Yates；j 必须从 i 开始
382. 链表随机节点中等水塘抽样 k=1
398. 随机数索引中等水塘抽样的变形
470. 用 Rand7() 实现 Rand10()中等拒绝采样
528. 按权重随机选择中等前缀和 + 二分

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。