一、题目[LeetCode-384]

给你一个整数数组 nums &＃xff0c;设计算法来打乱一个没有重复元素的数组。打乱后&＃xff0c;数组的所有排列应该是 等可能 的。

实现 Solution class:

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

示例 1&＃xff1a;

输入

["Solution", "shuffle", "reset", "shuffle"]

[[[1, 2, 3]], [], [], []]

输出

[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释

Solution solution &＃61; new Solution([1, 2, 3]);

solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如&＃xff0c;返回 [3, 1, 2]

solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]

solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如&＃xff0c;返回 [1, 3, 2]

提示&＃xff1a;

1. 1 <&＃61; nums.length <&＃61; 200
2. -10^6 <&＃61; nums[i] <&＃61; 10^6
3. nums 中的所有元素都是 唯一的
4. 最多可以调用 5 * 10^4 次 reset 和 shuffle

二、思路

依题意&＃xff0c;应当设计一个类&＃xff0c;其成员为一个vector数组对象nums。构造函数Solution()则应当将参数列表中的数组赋给类中的私有数组对象&＃xff08;浅拷贝即可&＃xff09;。reset()则直接返回nums即可。shuffle()要求返回一个将nums打乱的数组&＃xff0c;因此可先复制一个新数组&＃xff08;这里应当深拷贝&＃xff09;shuffleNums&＃xff0c;然后将其打乱&＃xff0c;可使用swap函数&＃xff0c;遍历新数组&＃xff0c;对于每一个shuffleNums[i]&＃xff0c;将其与任一shuffliNums[0, i-1]交换&＃xff08;可使用rand()%(i&＃43;1)方法取任一下标&＃xff09;&＃xff0c;这样可以达到随机打乱的效果。

class Solution {
public:Solution(vector& nums) {this->nums &＃61; nums;//构造函数&＃xff08;浅拷贝&＃xff09;}vector reset() {return nums;}vector shuffle() {vector shuffleNums(nums);//深拷贝一个数组shuffleNumsfor(int i &＃61; 0; i < shuffleNums.size(); i&＃43;&＃43;)swap(shuffleNums[i], shuffleNums[rand() % (i&＃43;1)]);return shuffleNums;}
private:vector nums;//指向参数列表中的nums&＃xff08;浅拷贝&＃xff09;
};/*** Your Solution object will be instantiated and called as such:* Solution* obj &＃61; new Solution(nums);* vector param_1 &＃61; obj->reset();* vector param_2 &＃61; obj->shuffle();*/

三、官方题解&＃xff08;来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;&＃xff09;

方法一&＃xff1a;暴力

首先&＃xff0c;我们考虑如何随机打乱一个数组。

不妨设数组 nums&＃xff0c;其长度为 n。我们可以使用如下方法打乱&＃xff1a;

将数组中所有的数都放到数据结构 waiting 中&＃xff0c;并初始化打乱后的数组 shuffle&＃xff1b;

循环 n 次&＃xff0c;在第 i 次循环中&＃xff08;0≤i

在 waiting 中随机抽取一个数 num&＃xff0c;将其作为打乱后的数组 shuffle 的第 i 个元素&＃xff1b;从 waiting 中移除 num。

对于原数组 nums 中的数 num 来说&＃xff0c;被移动到打乱后的数组的第 i 个位置的概率为&＃xff1a;

因此&＃xff0c;对于原数组 nums 中的任意一个数&＃xff0c;被移动到打乱后的数组的任意一个位置的概率都是相同的。

算法

在算法的实现中&＃xff0c;我们考虑以下两个问题&＃xff1a;

1.如何实现重设数组到它的初始状态&＃xff1f;

我们使用 nums 来存储当前数组&＃xff0c;并用 original 来存储数组的初始状态。在 需要重设数组到它的初始状态时&＃xff0c;只需要将 original 复制到 nums 并返回即 可。

2.如何实现 waiting&＃xff1f;

我们要求 waiting 既支持根据随机计算的下标获取元素&＃xff0c;又支持根据该下标 移除元素。在方法一中&＃xff0c;我们使用数组来实现 waiting。

class Solution {
public:Solution(vector& nums) {this->nums &＃61; nums;this->original.resize(nums.size());copy(nums.begin(), nums.end(), original.begin());}vector reset() {copy(original.begin(), original.end(), nums.begin());return nums;}vector shuffle() {vector shuffled &＃61; vector(nums.size());list lst(nums.begin(), nums.end());for (int i &＃61; 0; i private:vector nums;vector original;
};作者&＃xff1a;LeetCode-Solution
链接&＃xff1a;https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
著作权归作者所有。商业转载请联系作者获得授权&＃xff0c;非商业转载请注明出处。

复杂度分析

• 时间复杂度&＃xff1a;

1. 初始化&＃xff1a;O(n)&＃xff0c;其中 n 为数组中的元素数量。我们需要 O(n) 来初始化 original。
2. reset&＃xff1a;O(n)。我们需要 O(n) 将 original 复制到 nums。
3. shuffle&＃xff1a;O(n^2)。我们需要遍历 n 个元素&＃xff0c;每个元素需要 O(k) 的时间从 nums 中移除第 k 个元素。

• 空间复杂度&＃xff1a;O(n)。记录初始状态和临时的乱序数组均需要存储 n 个元素。

方法二&＃xff1a;Fisher-Yates 洗牌算法&＃xff08;即为上文的方法&＃xff09;

考虑通过调整 waiting 的实现方式以优化方法一。

我们可以在移除 waiting 的第 k 个元素时&＃xff0c;将第 k 个元素与数组的最后 1 个元素交换&＃xff0c;然后移除交换后数组的最后 1 个元素&＃xff0c;这样我们只需要 O(1) 的时间复杂度即可完成移除第 k 个元素的操作。此时&＃xff0c;被移除的交换后数组的最后 1 个元素即为我们根据随机下标获取的元素。

在此基础上&＃xff0c;我们也可以不移除最后 1 个元素&＃xff0c;而直接将其作为乱序后的结果&＃xff0c;并更新待乱序数组的长度&＃xff0c;从而实现数组的原地乱序。因为我们不再需要从数组中移除元素&＃xff0c;所以也可以将第 k 个元素与第 1 个元素交换。

具体地&＃xff0c;实现算法如下&＃xff1a;

1. 设待原地乱序的数组 nums。
2. 循环 n 次&＃xff0c;在第 i 次循环中&＃xff08;0≤i
3. 在 [i,n) 中随机抽取一个下标 j&＃xff1b;
4. 将第 i 个元素与第 j 个元素交换。

其中数组中的 nums[i .. n−1] 的部分为待乱序的数组&＃xff0c;其长度为 n−i&＃xff1b;nums[0 .. i−1] 的部分为乱序后的数组&＃xff0c;其长度为 i。

class Solution {
public:Solution(vector& nums) {this->nums &＃61; nums;this->original.resize(nums.size());copy(nums.begin(), nums.end(), original.begin());}vector reset() {copy(original.begin(), original.end(), nums.begin());return nums;}vector shuffle() {for (int i &＃61; 0; i private:vector nums;vector original;
};作者&＃xff1a;LeetCode-Solution
链接&＃xff1a;https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
著作权归作者所有。商业转载请联系作者获得授权&＃xff0c;非商业转载请注明出处。


复杂度分析

• 时间复杂度&＃xff1a;

1. 初始化&＃xff1a;O(n)&＃xff0c;其中 n 为数组中的元素数量。我们需要 O(n) 来初始化 original。
2. reset&＃xff1a;O(n)。我们需要 O(n) 将 original 复制到 nums。
3. shuffle&＃xff1a;O(n)。我们只需要遍历 n 个元素即可打乱数组。

• 空间复杂度&＃xff1a;O(n)。记录初始状态需要存储 n 个元素。

四、学习心得

数组打乱的两种方法&＃xff1a;

①暴力法&＃xff1a;循环n次&＃xff0c;对于第i次&＃xff08;从0计&＃xff09;&＃xff0c;在 waiting 中随机抽取一个数 num&＃xff0c;将其作为打乱后的数组 shuffle 的第 i 个元素&＃xff1b;从 waiting 中移除 num。

时间复杂度为O(n²)

②Fisher-Yates 洗牌算法&＃xff1a;原地遍历数组 nums n 次&＃xff0c;在第 i 次遍历中&＃xff08;从0计&＃xff09;&＃xff1a;在 [i,n) 中随机抽取一个下标 j&＃xff1b;将第 i 个元素与第 j 个元素交换。

时间复杂度为O(n)