给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums)使用整数数组nums初始化对象int[] reset()重设数组到它的初始状态并返回int[] shuffle()返回数组随机打乱后的结果
示例 1：
输入 ["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []] 输出 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]] 解释 Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2] solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3] solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
提示：
1 <= nums.length <= 50-106 <= nums[i] <= 106nums中的所有元素都是 唯一的- 最多可以调用
104次reset和shuffle
Related Topics
随机简单，可以参考下java.util.Collections#shuffle方法
核心：和前面的随机一位数字交换
class Solution {
int[] nums;
int[] shuffle;
public Solution(int[] nums) {
this.nums = nums;
}
public int[] reset() {
return nums;
}
public int[] shuffle() {
shuffle = nums.clone();
Random random = new Random();
for (int i = 0; i < shuffle.length; i++) {
swap(shuffle,i,random.nextInt(i+1));
}
return shuffle;
}
public void swap(int[] arr ,int x ,int y){
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
}看下java.util.Collections#shuffle(java.util.List<?>, java.util.Random)方法的源码，其实思想是一样的
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();
// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
// Dump array back into list
// instead of using a raw type here, it's possible to capture
// the wildcard but it will require a call to a supplementary
// private method
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
