题目

给你一个整数数组 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]

解答 & 代码

洗牌算法：
N 个数的全排列共 N! 种。
遍历数组设置每个位置的数，设当前遍历到下标 i：

则当前 [0,...,i-1] 部分已经是随机打乱的，而剩余的 [i,...,n-1] 部分则是待乱序的。因此随机从[i,...,n-1] 部分选择一个数，和第 i 个元素交换，则第 i 个元素填充完毕，继续遍历下一个元素 ```cpp class Solution { private: vector arr; public: Solution(vector& nums) {
```
  arr = nums;
```
}

vector reset() {
```
  return arr;
```
}

vector shuffle() {
```
  int len = arr.size();
  vector<int> shuffleArr(arr);
  for(int i = 0; i < len; ++i)
  {
      int idx = rand() % (len - i) + i;
      swap(shuffleArr[i], shuffleArr[idx]);
  }
  return shuffleArr;
```
} };

/**

Your Solution object will be instantiated and called as such:
Solution* obj = new Solution(nums);
vector param_1 = obj->reset();
vector param_2 = obj->shuffle(); */ `` 复杂度分析：设数组nums` 长为 N

时间复杂度：reset() 操作时间复杂度 O(1)，shuffle() 操作时间复杂度 O(N)
空间复杂度：reset() 操作空间复杂度 O(1)，shuffle() 操作空间复杂度 O(N)

执行结果：

执行结果：通过
执行用时：104 ms, 在所有 C++ 提交中击败了 47.86% 的用户
内存消耗：88.1 MB, 在所有 C++ 提交中击败了 62.63% 的用户

hot 100

[中等] 384. 打乱数组

题目

解答 & 代码