384 打乱数组

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

 

示例:

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

思路：
我们可以用一个简单的技巧来降低暴力算法的时间复杂度和空间复杂度，那就是让数组中的元素互相交换，这样就可以避免掉每次迭代中用于修改列表的时间了。

算法：
Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。

代码:

class Solution {
    private int[] array;
    private int[] original;
    Random rand = new Random();
    //将原始数组赋给array，并将原始数组拷贝一份保存至original
    public Solution(int[] nums) {
        this.array = nums;
        this.original = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return original;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i = 0; i< array.length; i++)
            //生成一个范围在当前下标到数组末尾元素下标之间的随机整数
            //并将当前元素和随机选出的下标所指的元素互相交换
            swapAt(i, randRange(i ,array.length));
        return array;
    }
    //此函数实现交换array数组的i处和j处的值
    private void swapAt(int i , int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //生成一个范围在min和max之间的随机整数
    private int randRange(int min, int max){
        return rand.nextInt(max - min) + min;
    }
}

复杂度分析
时间复杂度 ： O(n)
Fisher-Yates 洗牌算法时间复杂度是线性的，因为算法中生成随机序列，交换两个元素这两种操作都是常数时间复杂度的。
空间复杂度： O(n)
因为要实现 重置 功能，原始数组必须得保存一份，因此空间复杂度并没有优化。