LeetCode384之打乱数组(相关话题：随机算法，洗牌算法）

题目描述

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

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

输入[1, 2, 3]
输出 [3, 1, 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]

解法一

暴力算法简单的来说就是把每个数放在一个 ”帽子“ 里面，每次从 ”帽子“ 里面随机摸一个数出来，直到 “帽子” 为空。下面是具体操作，首先我们把数组 array 复制一份给数组 aux，之后每次随机从 aux 中取一个数，为了防止数被重复取出，每次取完就把这个数从 aux 中移除。重置 的实现方式很简单，只需把 array 恢复称最开始的状态就可以了。

这个算法的正确性在于，每次 for 循环中，任何一个元素都会以等可能的概率被选中。为了证明这一点，我们可以算出来，一个特定的元素 e 在第 k 轮被选中的概率为 P(e 在第 k 轮被选中) * P(e 在前 k 轮不被选中)。假设洗牌的数组有 n个元素，这个概率公式如下所