LeetCode 384. 打乱数组
目录
题目描述
题意分析
这是一道设计题。构造函数接收一个整数数组，之后要支持两个操作：
reset返回数组的初始排列，shuffle返回数组的一个随机排列，并且要求所有排列出现的可能性相同。两个方法都会被反复调用，调用顺序任意，reset之后可以再shuffle，shuffle之后也可以再reset。「所有排列相同概率」是这道题唯一的实质要求，也是唯一的判分点。它意味着答案不能只是「看起来乱」，而必须能说清楚每种排列恰好占
1/n!。一个只是随手交换若干次的实现，输出看上去毫无规律，却可能在概率上严重偏斜。约束方面，数组长度上限在几十的量级，调用次数上限在几万的量级，说明每次调用允许做一趟 $O(n)$ 的线性工作，不需要为单次操作做常数级的极致优化；但也说明
shuffle会被调用很多次，实现必须在多次调用之间保持行为一致，不能第一次正确、之后越来越偏。边界有两处需要提前想到：第一，
reset必须能在任意多次shuffle之后仍然还原出最初的排列，这要求对象内部始终留着一份没被污染的初始数据；第二，返回值是数组引用，调用方拿到后完全可能修改它，如果返回的正是内部持有的那份数据，一次外部修改就会毁掉后续所有调用的正确性。长度为1或0的数组是平凡情形，唯一的排列就是它本身。
解法：Fisher-Yates 洗牌
核心思路
题目的难点不是“打乱”，而是保证每个排列都以相同概率出现。直接随机交换若干次没有均匀性保证；Fisher-Yates 洗牌则把问题拆成一系列等概率选择。
从数组末尾向前处理。处理下标
i时，在尚未固定的区间[0, i]中等概率选一个下标j，再交换values[i]和values[j]。循环不变量是：每轮开始时，[i+1, n-1]已经固定，[0, i]恰好包含所有尚未放置的元素。交换后一个元素被固定到i，不变量继续成立。对任意目标排列，它的最后一位被选中的概率是
1/n，倒数第二位是1/(n-1)，依次类推，因此该排列出现的概率为
1/n × 1/(n-1) × ... × 1 = 1/n!所有排列概率相同，均匀性得证。设计上还要保存一份只读的初始快照：
shuffle只打乱副本，reset也返回副本，避免内部状态被洗牌过程或调用方修改。
解题步骤
- 构造时复制
nums保存为original，不直接持有调用方的数组引用。reset返回original的副本，保证外部修改返回值不会污染快照。shuffle先复制original得到工作数组values。- 令
i从n - 1递减到1；每轮在闭区间[0, i]随机选j，交换values[i]与values[j]。- 返回
values。例如[1,2,3]在i=2选中 0、在i=1选中 1，会得到[3,2,1]，这条路径的概率为1/3 × 1/2 = 1/6。
代码实现
class Solution {
private final int[] original;
public Solution(int[] nums) {
original = nums.clone();
}
public int[] reset() {
return original.clone();
}
public int[] shuffle() {
int[] values = original.clone();
for (int i = values.length - 1; i > 0; i--) {
int j = java.util.concurrent.ThreadLocalRandom.current().nextInt(i + 1);
int temp = values[i];
values[i] = values[j];
values[j] = temp;
}
return values;
}
}
import "math/rand"
type Solution struct {
original []int
}
func Constructor(nums []int) Solution {
return Solution{original: append([]int(nil), nums...)}
}
func (s *Solution) Reset() []int {
return append([]int(nil), s.original...)
}
func (s *Solution) Shuffle() []int {
values := append([]int(nil), s.original...)
for i := len(values) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
values[i], values[j] = values[j], values[i]
}
return values
}
复杂度分析
- 构造与
reset：时间复杂度均为 $O(n)$，用于复制数组。shuffle：时间复杂度 $O(n)$，每个位置只处理一次。- 空间复杂度：$O(n)$。对象保存初始快照，每次调用还会创建长度为
n的返回数组。
关键点总结
- Fisher-Yates 的随机范围必须是当前未固定区间
[0, i]，这样每一步都是从剩余元素中均匀选一个。- “每种排列概率为
1/n!”是均匀性的证明，不能用“结果看起来够乱”代替。original始终只读，所有洗牌都在副本上完成。- 数组跨越对象边界时返回副本，避免引用泄漏破坏后续调用。
易错点总结
- 写成
nextInt(i)会漏掉下标i，元素无法留在原位；必须使用nextInt(i + 1)。- 每轮都从整个
[0, n-1]取随机下标会破坏均匀分布。例如n=3时有3^3=27条等概率路径，无法平均分给 6 个排列。- 直接打乱
original会使reset无法恢复初始排列。reset直接返回内部数组时，调用方修改返回值会污染对象状态。- 不必特判长度为 0 或 1；循环条件
i > 0会自然处理。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 用哈希表加动态数组维持紧凑存储，删除时与末尾交换以保证等概率取值 |
| 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 | 困难 | 在 380 基础上允许重复值，需为每个值维护下标集合 |
| 382. 链表随机节点 | 中等 | 长度未知且不可随机访问，用蓄水池抽样以 1/t 的概率替换候选 |
| 398. 随机数索引 | 中等 | 在重复元素中等概率返回一个下标，同样是单次遍历的蓄水池抽样 |
| 470. 用 Rand7() 实现 Rand10() | 中等 | 从非均匀可用范围构造均匀分布，靠拒绝采样裁掉多余取值 |
| 528. 按权重随机选择 | 中等 | 目标是非均匀分布，用前缀和加二分把权重映射到区间 |
| 710. 黑名单中的随机数 | 困难 | 在挖去黑名单后的下标空间上均匀采样，靠映射把空洞填到尾部 |
| 478. 在圆内随机生成点 | 中等 | 连续空间上的均匀采样，需要对半径开方修正面积密度 |