LeetCode 384. 打乱数组

约 5 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 阿里 微软 美团 网易 快手 滴滴 虾皮
标签
数组 数学 设计 随机化

题目描述

✅ 384. 打乱数组

image-20260928204302149

image-20260928204302150

题意分析

为一个元素互不相同的数组实现两个操作：reset 返回最初的排列，shuffle 返回随机排列。随机的要求是每一种排列都以相同概率出现，并不要求每次都与上次不同，原排列本身也是合法结果。

打乱只改变位置，不能丢失或增加元素；多次打乱、重置之后，最初的顺序仍须能够恢复。因此要分别处理初始数据的保存，以及随机排列是否均匀这两个问题。

解法：Fisher-Yates 洗牌

核心思路

[!blue]

从数组末尾向前确定每个位置。处理下标 i 时，后缀 (i, n) 已经固定，剩余可选元素都在 [0, i]。在这 i + 1 个位置中均匀随机选一个下标 j，交换 values[i] 与 values[j]，就为位置 i 选定了一个元素。下一轮只处理更短的前缀，不再改变已经固定的后缀。

为什么每种排列等概率？固定任意目标排列，最后一个位置选到目标元素的概率为 1/n；在它已经选定的前提下，倒数第二个位置选对的概率为 1/(n - 1)，依次类推。全部位置都选对的概率为 1/n!，与目标排列是什么无关，所以所有排列等概率。这就是 Fisher-Yates 洗牌。

随机范围必须包含当前位置 i，因为当前元素也应该有机会留在原位；同时不能包含已经固定的后缀。Java 的 nextInt(i + 1) 和 Go 的 rand.Intn(i + 1) 都返回从 0 到 i 的随机整数，正好对应剩余候选范围。

构造对象时，把输入复制为只读快照 original。shuffle 每次复制快照后在副本上交换，reset 也返回快照的副本。这样外部修改输入数组或返回数组，都不会破坏后续恢复所依赖的初始排列。每次从同一快照开始不影响均匀性，因为新一轮的每个位置仍重新随机选择。

解题步骤

  1. 构造时复制输入数组，保存为 original。
  2. 调用 reset 时，复制并返回 original。
  3. 调用 shuffle 时，复制 original 得到工作数组 values。
  4. 让 i 从 n - 1 递减到 1，随机生成 0 <= j <= i，交换 values[i] 和 values[j]。
  5. 返回工作数组。最后剩余的位置已被唯一的剩余元素确定，无须再次随机选择。

代码实现

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 复制一次并完成 n - 1 轮交换，也是 $O(n)$。
  • 空间复杂度：对象保存初始快照需要 $O(n)$。每次 reset 或 shuffle 另创建一个 $O(n)$ 的返回数组；交换过程本身只使用 $O(1)$ 额外空间。

关键点总结

[!green]

  • 每轮从尚未固定的所有元素中均匀选一个，固定位置后缩小候选范围。
  • 任意目标排列的概率均为 1/n!，这是均匀性的依据，不能仅以看起来随机来判断。
  • 快照只读，构造、重置和打乱都注意数组复制，防止外部修改影响后续调用。

易错点总结

[!yellow]

  • 随机上界写成 i 会漏掉当前位置；这些接口的上界不包含在结果内，必须传 i + 1。
  • 每轮都从整个数组选下标，会重新干扰已固定的位置，无法沿用剩余元素等概率选择的保证。
  • 为了保证结果与原数组不同而重新洗牌，会把原排列排除，违背所有排列等概率的要求。
  • 直接打乱内部快照，或把快照本身作为返回值暴露出去，都可能使 reset 无法恢复初始顺序。

相似题目

题目 难度 关联与区别
382. 链表随机节点 中等 蓄水池抽样只随机保留一个候选，本题要随机排列全部元素，抽样空间不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/77298889
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！