2021-8-20 384. 打乱数组（洗牌算法）

本文主要是介绍2021-8-20 384. 打乱数组（洗牌算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：

题目：
给你一个整数数组 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
通过次数47,677提交次数82,987

题解：
思路
我们可以用一个简单的技巧来降低暴力算法的时间复杂度和空间复杂度，那就是让数组中的元素互相交换，这样就可以避免掉每次迭代中用于修改列表的时间了。

算法
Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。

此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 ，否则生成最后的排列组合的概率就不对了。

复杂度分析
时间复杂度： O(n)；Fisher-Yates 洗牌算法时间复杂度是线性的，因为算法中生成随机序列，交换两个元素这两种操作都是常数时间复杂度的。
空间复杂度： O(n)；因为要实现重置功能，原始数组必须得保存一份，因此空间复杂度并没有优化。

class Solution {
public:vector<int> randnums;vector<int> temp;void randall(vector<int> &randnums){int size=randnums.size();for(int i=0;i<size;i++){swap(randnums[i],randnums[i+rand()%(size-i)]);}return ;}Solution(vector<int>& nums) {randnums=nums;temp=nums;}/** Resets the array to its original configuration and return it. */vector<int> reset() {return temp;}/** Returns a random shuffling of the array. */vector<int> shuffle() {randall(randnums);return randnums;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(nums);* vector<int> param_1 = obj->reset();* vector<int> param_2 = obj->shuffle();*/