⭐ 题目日期：

腾讯 - 2024/10/11

🌳 题目描述：

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例 1：
输入
["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] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

对 Solution 初始化：

• 初始化原数组：存储原数组的数据 + 用于 reset 的返回值
• 初始化洗牌后的数组：克隆原数组中的数据，之后均操作洗牌数组，避免脏化原数组中的数据
• 初始化随机数生成器：Random, 用于随机洗牌，使每个数据在数组中的每个位置出现的概率相等

实现Reset：

• reset 实现的策略是重置，需要返回跟原数组一样的数据，我们选择返回原数组

实现 shuffle：

• 每次shuffle不需要都在原数组的基础上，从原数组出发，随机shuffle 1 次，再在shuffle后的数组上继续随机shuffle，数组里的每个元素在每个位置出现的概率依然相等。这是因为每次洗牌操作都是独立的，跟之前的状态无关，因此我们选择一直改动洗牌数组。

💻代码：

Java

    private int[] nums;
    private int[] shuffledNums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        shuffledNums = nums.clone();
        random = new Random();
    }

    public int[] reset() {
        return nums;
    }

    public int[] shuffle() {
        for (int i = shuffledNums.length - 1; i >= 0; i--) {
            int j = random.nextInt(0, i + 1);
            swap(i, j, shuffledNums);
        }
        return shuffledNums;
    }

     private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

🚵🏻复杂度分析：

时间复杂度：

1. reset: O(1), 直接返回原数组
2. shuffle: O(n), 循环n次，每次常数级操作

空间复杂度：O(n), 用于存储 shuffle 数组