题目链接

题目描述

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

示例：

输入
[“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 <= 200
-106 <= nums[i] <= 106
nums 中的所有元素都是 唯一的
最多可以调用 5 * 104 次 reset 和 shuffle

解题思路

方法一：Fisher-Yates 洗牌算法
在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。 ```java class Solution { int[] originArr; int[] shuffleArr; Random random = new Random(); public Solution(int[] nums) {
```
  originArr = new int[nums.length];
  shuffleArr = new int[nums.length];
  originArr = nums.clone();
```
} // 返回固定范围的随机值 [min,max) private int randomRange(int min,int max){
```
  return random.nextInt(max - min) + min;
```
} // 交换两个下标的元素 private void swapAt(int i,int j){
```
  int tmp = shuffleArr[i];
  shuffleArr[i] = shuffleArr[j];
  shuffleArr[j] = tmp;
```
} /* Resets the array to its original configuration and return it. / public int[] reset() {
```
  // 返回元素数组
  return originArr;
```
}

/* Returns a random shuffling of the array. / public int[] shuffle() {
```
  shuffleArr = originArr.clone();
  // 第i个元素和后面下标为[i,num.length)的元素进行随机交换
  for(int i = 0; i < originArr.length; ++i){
      swapAt(i,randomRange(i,originArr.length));
  }
  // 返回打乱后的数组
  return shuffleArr;
```
} }

/**

Your Solution object will be instantiated and called as such:
Solution obj = new Solution(nums);
int[] param_1 = obj.reset();
int[] param_2 = obj.shuffle(); */ ```

时间复杂度 O(n)
空间复杂度 O(n)

算法(leetcode 牛客网)

384. 打乱数组

题目链接

题目描述

解题思路

方法一：Fisher-Yates 洗牌算法