384.打乱数组

打乱数组

给你一个整数数组 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] <= 106
nums 中的所有元素都是 唯一的
最多可以调用 10^4 次 reset 和 shuffle

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shuffle-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

我看到第一眼的暴力解法是通过dfs找到所有可能的全排列并通过随机选取一个全排列来选取一个其中的一个全排列。时间复杂度是O(n!),因为所有全排列的数目为n!,全排列实际上就是遍历了所有的结果。
实际上的暴力解法为:

1. 将所有的数组元素拷贝到waiting list 中，并且初始化打乱后的数组shuffle
2. 循环n次，每次从waiting list中随机选取一个元素到shuffle的i位置并且从waiting list 中删除该元素
   从数学概率的角度上来看，数组中的元素被放置到shuffle位置i的概率为：
3. i= 0时，p[i] = \(\frac{1}{n}\)
4. i> 0时，p[i] = \((\frac{n-1}{n} \times \frac{n-2}{n-1} \times ··· \times \frac{n-i}{n-i+1})\times \frac{1}{n-i} = \frac{1}{n}\)
   这样每次shuffle的时间复杂度是\(O(n^2)\)的，之所以是\(O(n^2)\)的原因在于每次都需要移除固定的元素。
   洗牌算法是对暴力shuffle的优化。在选中第k个元素时，并不是将第k个元素移除，而是和最后一个元素交换位置，并且移除最后一个元素即可，就可以实现在O(1)的时间复杂度上移除元素的操作。并且进一步可以实现原地的shuffle，现在并不是将第k个元素和最后一个元素互换，而是和第一个元素交换位置，这样前面部分的数组就可以作为shuffle之后的数组，后面部分可以作为待乱序的数组。

code

class Solution {
public:

    vector<int> nums;

    Solution(vector<int>& nums) {
        this -> nums = nums;
    }
    
    vector<int> reset() {

        return nums;

    }
    
    vector<int> shuffle() {
        
        vector<int> ans = nums;

        for(int i = 0;i < ans.size();i ++)
        {
            int r = i + rand() % (ans.size() - i);
            if(r != i) swap(ans[r],ans[i]);
        }

        return ans;
    }
};

/**
 * 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();
 */