题目描述

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

样例

// 以数字集合 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();

算法1

(洗牌算法) $O(n)$

• 洗牌算法：对于数组的每一个元素，随机从这个元素以及后面的所有元素中选取一个元素与该元素交换。
• 正确性：一个数组全排列有$n!$种情况，所以洗牌算法也需要有$n!$种情况来满足排列的公平性。

数组：1，2，3，4
第一轮：选中1，在1,2,3中随机选取一个和1交换，例如3，得到3，2，1，4
第二轮：选中2，在2，1，3中随机选择一个数和2交换，例如4，得到3，4,1,2
第三轮：选中1，在1,2中随机选择一个数和1交换，例如2，得到3,4,2,1
第四轮：选中1，这轮可以省略

一共有$4·3·2·1$种情况，即$n!$种情况，符合随机的要求

Java 代码

class Solution {
    int[] deck;
    int[] backup;
    int n;
    Random r = new Random();
    public Solution(int[] nums) {
        n = nums.length;
        deck = new int[n];
        deck = nums;
        backup = nums.clone();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return backup;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i = 0; i < n; i++){
            int r = random(i,n);
            int tmp = deck[i];
            deck[i] = deck[r];
            deck[r] = tmp;
        }
        return deck;
    }

    private int random(int m, int n){
        return r.nextInt(n-m)+m;
    }
}