本题其实不算难，其实考点是对API的熟悉，读一读Java的Random Library就会有思路

    1. for (int j = copy.length; j > 0; --j) {
    2.   int idx = random.nextInt(j);
    3.   swap(copy, idx, j - 1);
    4. }

    上面就是核心代码，从后面到前面，一个个random选出，来填充。
    另一个难点是验证这个算法的正确性：

    • 第一次选，被选中的概率是384. Shuffle an Array - 图1
    • 第二次选，意味这第一次没有被选中，则概率是384. Shuffle an Array - 图2
    • 第三次选，同理，概率是384. Shuffle an Array - 图3

    • 同理可得，一个数 在 每个位置被选中的概率都是384. Shuffle an Array - 图4，所以这个算法是正确的

    • 时间复杂度：384. Shuffle an Array - 图5

    • 空间复杂度不讨论

    代码如下：

    1. class Solution {
    2.   private int[] original;
    3.   private Random random;
    5.   public Solution(int[] nums) {
    6.     original = nums.clone();
    7.     random = new Random();
    8.   }
    10.   /** Resets the array to its original configuration and return it. */
    11.   public int[] reset() {
    12.     return original;
    13.   }
    15.   /** Returns a random shuffling of the array. */
    16.   public int[] shuffle() {
    17.     int[] copy = original.clone();
    18.     for (int j = copy.length; j > 0; --j) {
    19.       int idx = random.nextInt(j);
    20.       swap(copy, idx, j - 1);
    21.     }
    22.     return copy;
    23.   }
    25.   private void swap(int[] array, int i, int j) {
    26.     int tmp = array[i];
    27.     array[i] = array[j];
    28.     array[j] = tmp;
    29.   }
    30. }
    32. /**
    33.  * Your Solution object will be instantiated and called as such:
    34.  * Solution obj = new Solution(nums);
    35.  * int[] param_1 = obj.reset();
    36.  * int[] param_2 = obj.shuffle();
    37.  */