DeepSeek LeetCode 384. 打乱数组 Java实现

LeetCode 384. 打乱数组 Java 实现

这道题的核心是 Fisher–Yates 洗牌算法（也叫 Knuth 洗牌算法），它能保证 n! 种排列等概率出现。

关键点

1. 保存原始数组的副本：reset() 要能恢复到初始状态，所以构造时必须克隆一份 original。
2. 每次 shuffle 都在副本上操作：不能在 original 上直接打乱，否则下次 reset() 就失效了。
3. Fisher–Yates 算法：从后往前遍历，对位置 i 随机选一个 [0, i] 范围内的 j，交换 arr[i] 和 arr[j]。

代码实现

classSolution{privateint[]original;// 保存初始数组privateRandomrandom;publicSolution(int[]nums){original=nums.clone();// 必须克隆，避免外部修改影响内部状态random=newRandom();}publicint[]reset(){returnoriginal.clone();// 返回副本，防止调用方修改内部数组}publicint[]shuffle(){int[]arr=original.clone();// 每次基于原始数组重新洗牌for(inti=arr.length-1;i>0;i--){intj=random.nextInt(i+1);// 生成 [0, i] 的随机下标inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}returnarr;}}

为什么这样是等概率的？

以 n = 3 为例，位置 2 有 3 种选择，位置 1 有 2 种选择，位置 0 只有 1 种选择，总共 3 × 2 × 1 = 3! = 6 种路径，每种路径对应一个唯一排列，且概率都是 1/6。推广到 n，每个排列的概率都是 1/n!，满足均匀分布。

常见错误

· ❌ 直接在 original 上打乱：会导致 reset() 无法恢复。
· ❌ 用「随机交换两个任意位置」的方式洗牌：当交换次数不固定或实现不当时，分布不均匀，某些排列出现概率更高。
· ❌ random.nextInt(i) 而不是 nextInt(i + 1)：范围少一个，位置 i 永远无法与自己交换，虽然理论上仍可能均匀但会破坏算法结构的正确性推导（且 i = 0 时会抛异常）。

复杂度分析

操作 时间复杂度 空间复杂度
构造 Solution O(n) O(n)
reset() O(n) O(n)（返回的副本）
shuffle() O(n) O(n)（返回的副本）

如果允许直接返回内部数组（不要求防御性拷贝），reset 和 shuffle 的额外空间可以降到 O(1)，但工程上返回副本更安全，也能避免评测系统拿到同一引用后互相干扰。