class Solution {
    int[] nums;
    int[] original;

    public Solution(int[] nums) {
        this.nums = nums;
        this.original = new int[nums.length];
        System.arraycopy(nums, 0, original, 0, nums.length);
    }

    public int[] reset() {
        System.arraycopy(original, 0, nums, 0, nums.length);
        return nums;
    }

    public int[] shuffle() {
        int[] shuffled = new int[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; ++i) {
            list.add(nums[i]);
        }
        Random random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            int j = random.nextInt(list.size());
            shuffled[i] = list.remove(j);
        }
        System.arraycopy(shuffled, 0, nums, 0, nums.length);
        return nums;
    }
}

¶复杂度分析

时间复杂度：

初始化：$O(n)$，其中 n 为数组中的元素数量。我们需要 $O(n)$ 来初始化原本数组，方便后续重置操作
reset()：$O(n)$，需要 $O(n)$ 进行数组的拷贝
shuffle()：$O(n^2)$，需要遍历 $n$ 个元素，每个元素需要 $O(n-k)$ 的时间从 nums 中移除第 $k$ 个元素

空间复杂度：${O(n)}$，记录初始状态和临时的乱序数组均需要存储 $n$ 个元素

¶Fisher-Yates 洗牌算法

上述算法的复杂度在于，每次随机化采样之后，需要删除原本位于 k 位置的元素，随后在新的数组进行重新随机采样，可以通过优化这种删除步骤做到提高时间复杂度的方法。比如，每次将删除的元素与数组的最后一个元素（第一个元素也可以）交换，随后重新在除去最后一个元素（第一个元素）的子数组重新采样，也可以达到最终效果，最终甚至做到了就地乱序

⛵具体的，实现算法如下（设需要原地乱序的数组为 nums ）：

循环 n 次（数组长度为 $n$）在第 $i$ 次循环中（$0 \le i < n$）：
在 $[i,n)$ 中随机抽取一个下标 $j$
将第 $i$ 个元素与第 $j$ 元素交换
如果完成 $n$ 次采样结束，否则返回第 1 步

¶官方代码

class Solution {
    int[] nums;
    int[] original;

    public Solution(int[] nums) {
        this.nums = nums;
        this.original = new int[nums.length];
        System.arraycopy(nums, 0, original, 0, nums.length);
    }

    public int[] reset() {
        System.arraycopy(original, 0, nums, 0, nums.length);
        return nums;
    }

    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            int j = i + random.nextInt(nums.length - i);
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
}

¶复杂度分析

时间复杂度：

初始化：$O(n)$，其中 n 为数组中的元素数量。我们需要 $O(n)$ 来初始化原本数组，方便后续重置操作
reset()：$O(n)$，需要 $O(n)$ 进行数组的拷贝
shuffle()：$O(n)$，只需要遍历 $n$ 个元素即可完成就地乱序

空间复杂度：${O(n)}$，记录初始状态需要存储 $n$ 个元素

¶0/1 发生器

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数
力扣470. 用 Rand7() 实现 Rand10()

简单粗暴的方法就是：将任意已知的随机数发生器，变为 0~1 发生器，随后通过 0~1 发生器产生出任意的随机数

public int rand10() {
    int res = 0;
    do{
        res = (zeroOne()<<3)+(zeroOne()<<2)+(zeroOne()<<1)+(zeroOne());
    }while(res>=10);
    return res+1;
}
public int zeroOne(){
    int temp = 0;
    do{
        temp = rand7();
    }while(temp==7);
    return temp>3?0:1;
}

也可以使用力扣官方的题解，使用拒绝采样的方法，每次随机是相互独立的，具体如下图：

随机算法

目录

¶打乱数组

¶暴力法

¶官方代码

¶复杂度分析

¶Fisher-Yates 洗牌算法

¶官方代码

¶复杂度分析

¶0/1 发生器

pineapple-man