LeetCode——打乱数组：洗牌算法

Q：打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

A:
以下部分引用自@labuladong的算法小抄：
此类算法都是靠随机选取元素交换来获取随机性，直接看代码（伪码），该算法有 4 种形式

// 得到⼀个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);
// 第⼀种写法
void shuffle(int[] arr) {
    int n = arr.length();
    /******** 区别只有这两⾏ ********/
    for (int i = 0 ; i < n; i++) {
    // 从 i 到最后随机选⼀个元素
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}
// 第⼆种写法
    for (int i = 0 ; i < n - 1; i++)
        int rand = randInt(i, n - 1);
// 第三种写法
    for (int i = n - 1 ; i >= 0; i--)
        int rand = randInt(0, i);
// 第四种写法
    for (int i = n - 1 ; i > 0; i--)
        int rand = randInt(0, i);

第二个和第四个写法都是减少最后一次1*1的交换。
分析洗牌算法正确性的准则：产⽣的结果必须有 (n!) 种可能，否则就是错误的。这个很好解释，因为⼀个⻓度为 n 的数组的全排列就有 (n!) 种，也就是说打乱结果总共有 (n!) 种。算法必须能够反映这个事实，才是正确的。
如果读者思考过洗牌算法，可能会想出如下的算法，但是这种写法是错误的：

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 每次都从闭区间 [0, n-1] 中随机选取元素进⾏交换
        int rand = randInt(0, n - 1);
        swap(arr[i], arr[rand]);
    }
}

现在你应该明⽩这种写法为什么会错误了。因为这种写法得到的所有可能结果有 (n^n) 种，⽽不是 (n!) 种，⽽且 (n^n) 不可能是 (n!) 的整数倍。

代码：

    private int[] array;
    private int[] original;

    Random rand = new Random();

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }

    /**
     * Resets the array to its original configuration and return it.
     */
    public int[] reset() {
        array = original;
        //这句是必然的，需要把array和original的地址分开，否则array一变，original也变
        original = original.clone();
        return original;
    }

    /**
     * Returns a random shuffling of the array.
     */
    public int[] shuffle() {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            int index = rand.nextInt(n - i) + i;
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
        return array;
    }