题目描述:

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

解法:

Knuth洗牌算法:
遍历一次数组, 在第 i 个位置的时候, 随机选取前面所有元素的第 j 个元素中的一个(包括自己), 然后交换.
这样轮询一遍之后数组就被打乱了, 且各个元素出现在各个位置的概率是相等的.

class Solution {

    private int[] nums;
    private Random random;
    private int length;
    
    public Solution(int[] nums) {
        this.nums = nums;
        this.length = nums.length;
        this.random = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] res = new int[length];
        for(int i=0; i<length; i++){
            res[i] = nums[i];
            // 选取第 j 个元素, 然后交换. 即可保证复制一遍完成后数组随机
            int j = random.nextInt(i+1);
            swap(res, i, j);
        }
        return res;
    }
    
    private void swap(int[] arr, int i, int j){
        if(i==j){
            return;
        }else{
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}