Given an array of integers (without any duplicates), shuffle the array such that all permutations are equally likely to be generated.

Assumptions

The given array is not null. We have the random generator to get random number.

Approach: use the random generator to get a random number, and then switch the index of this number with last index. then the size--.do the next loop.

public class Solution {
  public void shuffle(int[] array) {
    // Write your solution here.
    if (array == null || array.length == 0) {
      return;
    }
    int size = array.length;
    Random random = new Random();
    while (size > 0) {
      int n = random.nextInt(size);
      swap(array, n, size - 1);
      size--;
    }
  }

  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

Time: O(n);

Notice: Java 里的random的写法。 Math.random() . 0-1的long。 Or： Random random = new Random(). random.nextInt(n) [0,n)的随机数。