@@ -0,0 +1,1443 @@
+// Proof: Suppose this algorithm works, i.e. for each position j (starting from 0), the probability%0A// of any number in the range%5B0,j%5D to be at position j is 1/(1+j).%0A// Let's look at int i = random.nextInt(j + 1):%0A// 1. If i == j, nums%5Bj%5D does not need to change its position, which has probability 1/(1+j).%0A// 2. if i != j, nums%5Bj%5D needs to be swapped with nums%5Bi%5D. The probability of any number x in the%0A// range %5B0, j-1%5D to be at position j = nums%5Bj%5D changes its position =%3E%0A// x is at position i = (1-1/(1+j)) * (1/j) = 1/(1+j)%0A// Each number has equal probability to be at any position.%0Apublic class Solution %7B%0A  private Random random;%0A  private int%5B%5D original;%0A%0A  public Solution(int%5B%5D nums) %7B%0A    this.random = new Random();%0A    this.original = nums;%0A  %7D%0A%0A  /** Resets the array to its original configuration and return it. */%0A  public int%5B%5D reset() %7B%0A    return this.original;%0A  %7D%0A%0A  /** Returns a random shuffling of the array. */%0A  public int%5B%5D shuffle() %7B%0A    int%5B%5D arr = new int%5Bthis.original.length%5D;%0A    System.arraycopy(this.original, 0, arr, 0, this.original.length);%0A    for (int i = arr.length - 1; i %3E 0; i--) %7B%0A      int j = this.random.nextInt(i + 1);%0A      int t = arr%5Bi%5D;%0A      arr%5Bi%5D = arr%5Bj%5D;%0A      arr%5Bj%5D = t;%0A    %7D%0A    return arr;%0A  %7D%0A%7D%0A%0A/**%0A * Your Solution object will be instantiated and called as such:%0A * Solution obj = new Solution(nums);%0A * int%5B%5D param_1 = obj.reset();%0A * int%5B%5D param_2 = obj.shuffle();%0A */%0A

add solution