DeepSeek LeetCode 384. 打乱数组 Java实现

LeetCode 384. 打乱数组 Java 实现这道题的核心是 Fisher–Yates 洗牌算法也叫 Knuth 洗牌算法它能保证 n! 种排列等概率出现。关键点保存原始数组的副本reset() 要能恢复到初始状态所以构造时必须克隆一份 original。每次 shuffle 都在副本上操作不能在 original 上直接打乱否则下次 reset() 就失效了。Fisher–Yates 算法从后往前遍历对位置 i 随机选一个 [0, i] 范围内的 j交换 arr[i] 和 arr[j]。代码实现classSolution{privateint[]original;// 保存初始数组privateRandomrandom;publicSolution(int[]nums){originalnums.clone();// 必须克隆避免外部修改影响内部状态randomnewRandom();}publicint[]reset(){returnoriginal.clone();// 返回副本防止调用方修改内部数组}publicint[]shuffle(){int[]arroriginal.clone();// 每次基于原始数组重新洗牌for(intiarr.length-1;i0;i--){intjrandom.nextInt(i1);// 生成 [0, i] 的随机下标inttemparr[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)但工程上返回副本更安全也能避免评测系统拿到同一引用后互相干扰。