#384. 打乱数组

LeetCode 原题链接

#1. 题目描述

给定一个整数数组 nums，设计一个支持重置和随机打乱的类：

• reset()：将数组恢复为传入构造函数时的初始状态并返回。
• shuffle()：返回数组的一个随机排列，要求每一种排列出现的概率相同。

示例：

输入：
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]

可能的输出：
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释：
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 返回 [1, 2, 3] 的一个随机排列
solution.reset();   // 返回初始数组 [1, 2, 3]
solution.shuffle(); // 再次返回一个随机排列

输出不唯一，但长度为 n 且元素互不相同的数组应当有 n! 种可能排列，每种排列出现的概率都应为 1 / n!。

这道题及其常见追问包括：

• 如何原地乱序，使额外空间复杂度为 O(1)？
• 为什么 array.sort(() => Math.random() - 0.5) 不可靠？
• 如何证明洗牌结果是等概率的？
• 如何从数组中无重复地随机选出 k 个元素？
• 如何让测试中的乱序结果可复现？

#2. 题型判断

这是一个随机算法与数组原地交换问题。标准解法是 Fisher–Yates 洗牌算法。

算法从数组末尾开始，依次确定每个位置上的元素。处理下标 i 时，在尚未确定的区间 [0, i] 中等概率选择一个下标 j，交换 array[i] 和 array[j]。

不能简单使用下面的写法：

array.sort(() => Math.random() - 0.5);

排序算法要求比较函数对元素给出稳定、一致的顺序关系，但随机比较器对同一对元素可能返回不同结果。最终分布会受到排序实现和比较过程影响，不能保证所有排列等概率出现。

#3. 核心思路

假设数组长度为 n，从 i = n - 1 开始向前处理：

1. 从 [0, i] 中随机选择整数 j。
2. 交换下标 i 和 j 对应的元素。
3. 交换后，下标 i 的元素已经确定，不再参与后续选择。
4. 继续处理 [0, i - 1]，直到 i = 1。

选择范围必须包含 i 自身。若只从 [0, i - 1] 中选择，当前位置每轮都被强制交换，就会遗漏部分排列。例如长度为 2 的数组将永远无法保持原顺序。

#为什么从后向前遍历

倒序遍历维护了一个清晰的不变量：

每轮开始时，区间 [0, i] 中的元素尚未确定，区间 [i + 1, n - 1] 已经完成随机放置，后续不会再被修改。

处理下标 i 时，从所有尚未确定的元素中等概率选一个放到 i。交换完成后，i 被划入右侧的已确定区间，下一轮只处理 [0, i - 1]。

最后下标 0 只剩一个元素，不需要交换。因此每个位置只确定一次，已经确定的结果不会被后续操作破坏。

从前向后同样可以实现 Fisher–Yates，但随机范围必须相应改为尚未确定的 [i, n - 1]。不能只改变遍历方向，却继续使用 [0, i]。

#为什么计算 j 时使用 i + 1

Math.random() 的取值范围是左闭右开区间 [0, 1)。处理下标 i 时，需要从闭区间 [0, i] 中选择，一共有 i + 1 个候选下标：

0, 1, 2, ..., i

所以 Math.random() * (i + 1) 的范围是 [0, i + 1)，再经过 Math.floor()，恰好得到从 0 到 i 的所有整数：

const j = Math.floor(Math.random() * (i + 1));

必须允许 j === i，因为“当前位置保持不动”也是一个合法的随机结果。如果误写为 Math.random() * i，只能得到 [0, i - 1]，当前位置会被强制交换。以两个元素为例，每次都只能交换，原顺序出现的概率会变成 0，不再是等概率洗牌。

#4. 示例步骤图解

以 [1, 2, 3, 4] 为例，假设三轮随机选出的下标依次为 1、0、1：

最终得到 [3, 4, 1, 2]。

#5. 变量与区间含义

• i：当前要确定的位置；(i, n - 1] 已完成乱序且不再修改。
• [0, i]：仍未确定的候选区间。
• j：从 [0, i] 中等概率选出的随机下标。
• array：被原地打乱的数组。

生成闭区间 [0, i] 内随机整数的写法是：

const j = Math.floor(random() * (i + 1));

其中 random() 返回 [0, 1) 范围内的随机数。

#6. 推进规则与等概率证明

每轮从尚未确定的元素中等概率选出一个，放到当前末尾位置。

对于任意一个指定排列：

• 最后一个位置选中特定元素的概率为 1 / n。
• 倒数第二个位置从剩余元素中选中特定元素的概率为 1 / (n - 1)。
• 后续概率依次为 1 / (n - 2)，直到 1 / 1。

因此生成这个指定排列的概率为：

1/n × 1/(n-1) × ... × 1/1 = 1/n!

所有排列都对应唯一的一组选取过程，所以每一种排列的概率相同。

#7. 边界条件与易错点

• 空数组和只有一个元素的数组不需要交换。
• 随机下标必须从闭区间 [0, i] 中选择。
• 循环执行到 i > 0 即可，下标 0 会自然成为最后剩余的元素。
• 题目要求保留原数组时，应先浅拷贝再乱序。
• Math.random() 适合普通面试题、动画和非安全场景，不适合抽奖、令牌或密码学场景；安全场景应使用平台提供的密码学安全随机数生成器。
• 随机算法的单元测试不应断言某次调用得到固定排列，可以注入可控的 random 函数进行测试。

#8. 代码实现

#LeetCode 实现

var Solution = function (nums) {
  this.original = [...nums];
};

Solution.prototype.reset = function () {
  return [...this.original];
};

Solution.prototype.shuffle = function () {
  const result = [...this.original];

  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }

  return result;
};

构造函数保存初始数组的副本。reset() 和 shuffle() 都返回新数组，避免调用方修改返回值后破坏内部保存的初始状态。

#可注入随机源的通用实现

function shuffle(array, random = Math.random) {
  const result = [...array];

  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }

  return result;
}

注入 random 后，可以在单元测试中传入固定的随机数序列，让结果可复现。

#无重复随机选取 k 个元素

如果只需要随机选择 k 个元素，不必打乱整个数组。执行前 k 轮 Fisher–Yates，然后返回已确定的尾部区间即可。

function sample(array, k, random = Math.random) {
  if (!Number.isInteger(k) || k < 0 || k > array.length) {
    throw new RangeError('k must be an integer between 0 and array.length');
  }

  const result = [...array];

  for (let i = result.length - 1; i >= result.length - k; i--) {
    const j = Math.floor(random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }

  return result.slice(result.length - k);
}

当 k 远小于 n 时，交换部分只需要 O(k) 时间；由于这里保留原数组，复制数组仍需要 O(n) 时间和空间。若允许修改原数组，抽样过程本身可以做到 O(k) 时间和 O(1) 额外空间。

#9. 复杂度分析

对于 LeetCode 384 的实现：

• 构造函数时间和空间复杂度：O(n)。
• reset() 时间和返回结果所需空间复杂度：O(n)。
• shuffle() 时间和返回结果所需空间复杂度：O(n)。
• 若题目允许直接修改原数组，Fisher–Yates 算法本身的额外空间复杂度为 O(1)。

与随机排序相比，Fisher–Yates 的复杂度更低、行为不依赖排序引擎，并且能够从算法上证明所有排列等概率出现。